剑指Offer Day7 2020-02-25

1.反转链表

题目：
输入一个链表，反转链表后，输出新链表的表头。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p1 = null;
        ListNode p2 = head;
        while (p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }
        return p1;
    }
}

搞不清三个指针的计算过程！

递归方法

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 1,2,3,4,5
        ListNode newHead = ReverseList(head.next); // head = 4; head.next = 5; newHead = 5
        head.next.next = head; // 5.next = 4
        head.next = null;//4.next = null
        return newHead; // 5->4->null
    }
}

2.合并两个排序的链表

题目
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 1,3,5,7
        // 2,4,6,8
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode newHead = null;
        if (list1.val < list2.val) {
            newHead = list1;
            newHead.next =  Merge(list1.next, list2);
        } else {
            newHead = list2;
            newHead.next =  Merge(list1, list2.next);
        }
        return newHead;
    }
}

不清楚返回值和递归过程还有什么时候创建新结点！