題目匯總https://leetcode-cn.com/tag/linked-list/

2. 兩數(shù)相加中等

19. 刪除鏈表的倒數(shù)第N個節(jié)點中等 [?]

21. 合并兩個有序鏈表簡單 [?]

23. 合并K個排序鏈表困難(沒有做)

24. 兩兩交換鏈表中的節(jié)點中等[?]

25. K 個一組翻轉(zhuǎn)鏈表困難(沒有做)

61. 旋轉(zhuǎn)鏈表中等

82. 刪除排序鏈表中的重復(fù)元素 II中等

83. 刪除排序鏈表中的重復(fù)元素簡單[?]

86. 分隔鏈表中等[?]

2. 兩數(shù)相加中等

給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：

見精選解題

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while(l1!=null || l2!=null){
            int i = (l1 != null) ? l1.val : 0;
            int j = (l2 != null) ? l2.val : 0;
            int sum = i + j + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;
 
            if(l1!=null)
                l1 = l1.next;
            if(l2!=null)
                l2 = l2.next;
        }
       
        if(carry==1)
            cur.next = new ListNode(carry);
    return pre.next;
    }
}

19. 刪除鏈表的倒數(shù)第N個節(jié)點中等 [?]

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：給定的 n 保證是有效的。
進階：你能嘗試使用一趟掃描實現(xiàn)嗎？

思路一：兩次遍歷

刪除鏈表的倒數(shù)第N個結(jié)點相當(dāng)于刪除鏈表的第(L-N+1)個結(jié)點。第一次遍歷得出鏈表的長度L，啞結(jié)點的設(shè)置非常有必要。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = head;
        int length = 0;
        while(first!=null){
            first = first.next;
            length++; 
        }
        length = length - n;
        first = dummy;
        while(length>0){
            first = first.next;
            length--;
            
        }
        first.next = first.next.next;
    return dummy.next;
    }
}

思路二：一次遍歷

使用兩個指針，兩個指針之間保持恒定的間隔，當(dāng)?shù)谝粋€指針到達最后一個結(jié)點時，第二個指針將指向從最后一個結(jié)點數(shù)起的第 n 個結(jié)點。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //設(shè)置啞結(jié)點
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = head;
        ListNode second = head;
        //第一個指針先指向第(l-n+2)個結(jié)點，即要刪除的結(jié)點的前一個結(jié)點
        for(int i=1;i<=n+1;i++){
            first = first.next;
        }
        //兩個指針一起移動，第二個指針指向要刪除的結(jié)點
        while(first!=null){
            first = first.next;
            second = second.next;
        }
        //此時刪除結(jié)點
        second.next = second.next.next;

    return dummy.next;
    }
}

21. 合并兩個有序鏈表簡單 [?]

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路：直接歸并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dummy = new ListNode(-1);
       ListNode cur = dummy;
       while(l1!=null&&l2!=null){
           if(l1.val <= l2.val){
               cur.next = l1;
               l1 = l1.next;
           }else{
               cur.next = l2;
               l2 = l2.next;
           }
           cur = cur.next;
       }
       //一個鏈表為空
       if(l1==null){
             cur.next = l2;
        }
        else if(l2==null){
            cur.next = l1;
        } 
    return dummy.next;
    }
}

思路二：遞歸

兩個鏈表頭部較小的一個與剩下元素的 merge 操作結(jié)果合并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    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;
        }

    }
}

23. 合并K個排序鏈表困難

合并 k個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。
輸入:
[
1->4->5,
1->3->4,
2->6
]
輸出: 1->1->2->3->4->4->5->6

24. 兩兩交換鏈表中的節(jié)點中等[?]

給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.

思路一：非遞歸

見

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        pre.next = head;
        while(pre.next!=null&&pre.next.next!=null){
            ListNode t = pre.next.next;
            pre.next.next = t.next;
            t.next = pre.next;
            pre.next = t;
            pre = t.next;
        }
    return dummy.next;
    }
}

思路二：遞歸

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode first = head;
        ListNode second = head.next;
        head = second;
        first.next = swapPairs(second.next);
        second.next = first;
    return head;

    }
}

25. K 個一組翻轉(zhuǎn)鏈表困難

給你一個鏈表，每 k個節(jié)點一組進行翻轉(zhuǎn)，請你返回翻轉(zhuǎn)后的鏈表。
k是一個正整數(shù)，它的值小于或等于鏈表的長度。
如果節(jié)點總數(shù)不是 k的整數(shù)倍，那么請將最后剩余的節(jié)點保持原有順序。
給你這個鏈表：1->2->3->4->5
當(dāng) k= 2 時，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k= 3 時，應(yīng)當(dāng)返回: 3->2->1->4->5
說明：
你的算法只能使用常數(shù)的額外空間。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際進行節(jié)點交換。

61. 旋轉(zhuǎn)鏈表中等

給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動 k個位置，其中 k是非負數(shù)。
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

思路：

找到鏈表的表尾，表尾指向表頭，將鏈表閉合成環(huán)，再確定新的鏈表頭和鏈表尾

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) 
            return null;
        if (head.next == null) 
            return head;
        ListNode cur = head;
        int length = 1;
        while(cur.next!=null){
            length++;
            cur = cur.next;
        }
        cur.next = head;//鏈表連成環(huán)
        for(int i=0;i<length-k%length;i++){
            cur = cur.next;
        }
        ListNode new_head = cur.next;//找到新的鏈表頭
        cur.next = null;//斷開
    return new_head;

    }
}

82. 刪除排序鏈表中的重復(fù)元素 II中等

給定一個排序鏈表，刪除所有含有重復(fù)數(shù)字的節(jié)點，只保留原始鏈表中沒有重復(fù)出現(xiàn)的數(shù)字。
輸入: 1->2->3->3->4->4->5
輸出: 1->2->5

思路：

創(chuàng)建一個臨時指針temp

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next!=null&&cur.next.next!=null){
            ListNode temp = cur.next;
            if(cur.next.val == cur.next.next.val){
                while (temp != null && temp.next != null && temp.val == temp.next.val ) {
                    temp = temp.next;
                }
                cur.next = temp.next;
            } 
            else
                cur = cur.next;
            }   
    return dummy.next;
   
    }
}

83. 刪除排序鏈表中的重復(fù)元素簡單[?]

給定一個排序鏈表，刪除所有重復(fù)的元素，使得每個元素只出現(xiàn)一次。
輸入: 1->1->2
輸出: 1->2

思路：

比較當(dāng)前結(jié)點的值和它之后的結(jié)點值確定它是否為重復(fù)結(jié)點。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

86. 分隔鏈表中等[?]

給定一個鏈表和一個特定值x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。
你應(yīng)當(dāng)保留兩個分區(qū)中每個節(jié)點的初始相對位置。
輸入: head = 1->4->3->2->5->2, x = 3
輸出: 1->2->2->4->3->5

思路：雙指針

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶，2020/08/06
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(0);
        ListNode before = beforeHead;
        ListNode afterHead = new ListNode(0);
        ListNode after = afterHead;
        while(head != null){
            if(head.val < x){
                before.next = head;
                before = before.next;
            }else{
                after.next = head;
                after = after.next;
            }
            head = head.next;   
        }
        before.next = afterHead.next;
        after.next = null;
    return beforeHead.next;
    }
}