• 解題思路：遞歸的兩個條件：

1. 終止條件是當(dāng)前節(jié)點或者下一個節(jié)點==null
2. 在函數(shù)內(nèi)部，改變節(jié)點的指向，也就是 head 的下一個節(jié)點指向 head 遞歸函數(shù)那句 head.next.next = head

public ListNode reverseList(ListNode head) {
        //遞歸終止條件是當(dāng)前為空，或者下一個節(jié)點為空
        if(head==null || head.next==null) {
            return head;
        }
        //這里的cur就是最后一個節(jié)點
        ListNode cur = reverseList(head.next);
        //這里請配合動畫演示理解
        //如果鏈表是 1->2->3->4->5，那么此時的cur就是5
        //而head是4，head的下一個是5，下下一個是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止鏈表循環(huán)，需要將head.next設(shè)置為空
        head.next = null;
        //每層遞歸函數(shù)都返回cur，也就是最后一個節(jié)點
        return cur;
    }

三、LeetCode-21、合并兩個有序鏈表

1、遞歸方法解題

• 解題思路：取出來一個數(shù)之后，剩下的仍然是這道題的一個問題，因此可以使用遞歸。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

2、迭代方法解題

• 解題思路：首先，我們設(shè)定一個哨兵節(jié)點 "prehead" ，這可以在最后讓我們比較容易地返回合并后的鏈表。我們維護一個 prev 指針，我們需要做的是調(diào)整它的 next 指針。然后，我們重復(fù)以下過程，直到 l1 或者 l2 指向了 null ：如果 l1 當(dāng)前位置的值小于等于 l2 ，我們就把 l1 的值接在 prev 節(jié)點的后面同時將 l1 指針往后移一個。否則，我們對 l2 做同樣的操作。不管我們將哪一個元素接在了后面，我們都把 prev 向后移一個元素。
• 在循環(huán)終止的時候， l1 和 l2 至多有一個是非空的。由于輸入的兩個鏈表都是有序的，所以不管哪個鏈表是非空的，它包含的所有元素都比前面已經(jīng)合并鏈表中的所有元素都要大。這意味著我們只需要簡單地將非空鏈表接在合并鏈表的后面，并返回合并鏈表。
• 問題：這個和一開始我自己想的是一樣的，但是這段代碼沒有考慮存在空鏈表的情況，只考慮了都存在的情況
• 另外對于怎樣存儲頭節(jié)點：這里的方法很好，可以先建一個已知數(shù)據(jù)的一個節(jié)點，最終返回該節(jié)點的next即使頭節(jié)點

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // maintain an unchanging reference to node ahead of the return node.
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // exactly one of l1 and l2 can be non-null at this point, so connect
        // the non-null list to the end of the merged list.
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;

四、LeetCode-26、刪除排序數(shù)組中的重復(fù)項

1、雙指針迭代

• 解題思路：我們可以申請兩個指針，第一個指針叫i，最初是指向0的。第二個指針 j 指向 1，然后不斷遍歷數(shù)組。每次判斷如果相等，那么i就不動，一直增長j，j肯定是比ida，遇到不等的時候?qū)的值賦值給i，最終返回i+1。

public int removeDuplicates(int[] nums) {
       int i=0;
       for(int j=1;j<nums.length;j++){
           if(nums[i]!=nums[j]){
               i++;
               nums[i]=nums[j];
           }
       }
       return i+1;
    }

2、System.arraycopy()方法的使用

• 解題思路：在循環(huán)體中控制循環(huán)條件，因為移動了數(shù)組后面的值，因此i要減1，重新怕段i和 后一個值得關(guān)系，不然會錯過一個數(shù)。

    public int removeDuplicates(int[] nums) {
       int len=nums.length;
       for(int i=0;i<len-1;i++){
           if(nums[i]==nums[i+1]){
               System.arraycopy(nums,i+1,nums,i,len-i-1);
               len--;
               i--;
           }
       }
       return len;
    }

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/