参考刷题指南

GitHub-CyC2018/Leetcode题解之链表

160. 相交链表

超高复杂度的暴力遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode B = headB;

        while (headA != null){
            while (headB !=null){
                if (headA == headB) return headA;
                else headB = headB.next;
            }
            headA = headA.next;
            headB = B;
        }

        return null;
    }
}

双指针技巧：

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。如果不存在交点，那么 a + b = b + a，会同时到达链表尾部的 null，从而退出循环。

两个人速度一致， 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话，那么这段路上俩人肯定是肩并肩手牵手的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != curB){
            if (curA != null) curA = curA.next;
            else curA = headB;

            if (curB != null) curB = curB.next;
            else curB = headA;
        }

        return curA;
    }
}

206. 反转链表

递归：

学习：labuladong讲的递归反转链表专题

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

迭代：

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null){
            ListNode nextTemp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextTemp;
        }

        return prev;
    }
}

92. 反转链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) return reverseN(head, right);
        
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode after = null;

    ListNode reverseN(ListNode head, int n){
        if (n == 1) {
            after = head.next;
            return head;
        }

        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = after;

        return last;
    }
}

25. K 个一组翻转链表

参考labuladong教程：如何k个一组反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a = head, b = head;

        for (int i = 0; i < k; i++){
            if (b == null) return head;
            b = b.next;
        }

        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode reverse(ListNode a, ListNode b){
        ListNode pre = null, cur = a, nxt = a;
        while (cur != b){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

234. 回文链表

参考labuladong教程：如何高效判断回文链表

最暴力法，把链表整个翻转后两个链表一一比对：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode headTemp = copyList(head);
        ListNode re = reverse(headTemp);

        while (head != null){
            if (re.val != head.val) return false;
            re = re.next;
            head = head.next;
        }
        return true;
    }

    ListNode reverse(ListNode head){
        if (head == null || head.next == null) return head;

        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;

        return last;
    }

    ListNode copyList(ListNode head){
        if (head == null) return null;

        ListNode newCur = new ListNode(head.val, null);
        ListNode newHead = newCur, cur = head;

        while (cur.next != null){
            ListNode newNode = new ListNode(cur.next.val, null);
            newCur.next = newNode;

            newCur = newCur.next;
            cur = cur.next;
        }
        return newHead;
    }
}

之所以需要copyList这个方法是因为ListNode headTemp = head;并不能拷贝一个全新的链表，以至于在reverse方法里无论传入head还是headTemp到最后都会破坏链表结构，因此无法从re跟head开始同时遍历比较。参考：Java如何完全复制一个对象

所以下面第三种找中点后翻转后半部分的方法，没有破坏前半部分的链表结构，则可以直接ListNode right = reverse(slow);接收翻转后的头结点，进行比较。

递归倒序遍历单链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    ListNode left;

    public boolean isPalindrome(ListNode head) {
        left = head;

        return reverse(head);
    }

    boolean reverse(ListNode right){
        if (right == null) return true;

        boolean flag = reverse(right.next);
        flag = flag && (right.val == left.val);

        left = left.next;

        return flag;
    }
}

快慢指针找中点，反转后半部分链表，减少空间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;

        ListNode left = head;
        ListNode right = reverse(slow);

        while (right != null){//这里必须是right而不是left，是因为如果长度是偶数的话，两边指针到达中点后left进入原链表的后半部分，而right进入已翻转的后半部分链表的队尾null指针，如果是left!=null的话不会跳出循环，而right进入null状态后.val调用报错！	
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }

    ListNode reverse(ListNode head){
        if (head == null || head.next == null) return head;

        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;

        return last;
    }
}

21. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1;

        if (l1.val > l2.val){
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
        else{
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
    }
}

83. 删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;

        ListNode cur = head;

        while (cur != null && cur.next != null){
            if (cur.val == cur.next.val){
                while (cur.next != null && cur.val == cur.next.val) cur.next = cur.next.next;
            }
            cur = cur.next;
        }

        return head;
    }
}

递归解法：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);

        if (head.val == head.next.val) return head.next;//如果值相等，取后面已经deleteDuplicates好的那个（不同于迭代法取最前面那个）
        else return head;

    }
}

19. 删除链表的倒数第 N 个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head, fast = head;

        for (int i = 0; i < n; i++) fast = fast.next;

        if (fast == null) return slow.next;

        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        ListNode pre = slow;
        slow = slow.next;
        pre.next = slow.next;//其实这三句话可以用一句话代替：slow.next = slow.next.next，因为只是删除slow.next结点
        
        return head;
    }
}

24. 两两交换链表中的节点

直接套用k个一组翻转链表的代码（k=2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public ListNode swapPairs(ListNode head) {
        head = reverseKGroup(head, 2);
        return head;
    }

    ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a = head, b = head;

        for (int i = 0; i < k; i++){
            if (b == null) return head;
            b = b.next;
        }

        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode reverse(ListNode a, ListNode b){
        ListNode pre = null, cur = a, nxt = a;
        while (cur != b){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

同样的思路，简化版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head == null ? null : head;
        ListNode a = head, b = head.next.next;

        ListNode newHead = swap(a, a.next);
        a.next = swapPairs(b);

        return newHead;
    }

    ListNode swap(ListNode a, ListNode b){
        a.next = b.next;
        b.next = a;
        return b;
    }
}

2. 两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        ListNode cur = new ListNode();
        ListNode head = cur, pre = null;

        while (l1 != null || l2 != null){
            int val1 = 0, val2 = 0;
            if (l1 != null) val1 = l1.val;
            if (l2 != null) val2 = l2.val;

            if (val1 + val2 + add >= 10){
                cur.val = val1 + val2 + add - 10;
                add = 1;
            }
            else{
                cur.val = val1 + val2 + add;
                add = 0;
            }

            ListNode nxt = new ListNode();
            cur.next = nxt;
            pre = cur;
            cur = cur.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (add == 1) cur.val = add;
        else pre.next = null;

        return head;
    }
}

445. 两数相加 II

暴力翻转链表后做按位加法然后再转回来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode rel1 = reverse(l1), rel2 = reverse(l2);

        boolean flag = false;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (rel1 != null || rel2 != null){
            int add;
            if (flag) add = 1;
            else add = 0;

            if (rel1 == null){
                if (rel2.val + add >= 10){
                    flag = true;
                    cur.val = rel2.val - 10 + add;
                }
                else{
                    flag = false;
                    cur.val = rel2.val + add;
                }
                rel2 = rel2.next;
            }
            else if (rel2 == null){
                if (rel1.val + add >= 10){
                    flag = true;
                    cur.val = rel1.val - 10 + add;
                }
                else{
                    flag = false;
                    cur.val = rel1.val + add;
                }
                rel1 = rel1.next;
            }
            else{
                if (rel1.val + rel2.val + add >= 10){
                    flag = true;
                    cur.val = rel1.val + rel2.val - 10 + add;
                }
                else{
                    flag = false;
                    cur.val = rel1.val + rel2.val + add;
                }
                rel1 = rel1.next;
                rel2 = rel2.next;
            }

            ListNode nxt = new ListNode(0);
            cur.next = nxt;
            cur = cur.next;
        }

        if (!flag){
            ListNode newHead = reverse(head);
            return newHead.next;
        }
        else {
            cur.val = 1;
            ListNode newHead = reverse(head);
            return newHead;
        }
    }

    ListNode reverse(ListNode head){
        if (head == null || head.next == null) return head;

        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;

        return last;
    }
}

输入链表不能修改的条件下，用栈解决，把所有数字压入栈中再依次取出相加：

！！对于链表逆序处理应该首先想到栈！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1Val = new Stack<>();
        Stack<Integer> l2Val = new Stack<>();

        while (l1 != null){
            l1Val.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            l2Val.push(l2.val);
            l2 = l2.next;
        }

        int add = 0;

        ListNode cur = new ListNode();

        while (!l1Val.isEmpty() || !l2Val.isEmpty()){
            int val1 = 0, val2 = 0;
            if (l1Val.isEmpty() && !l2Val.isEmpty()) val2 = l2Val.pop();
            else if (l2Val.isEmpty() && !l1Val.isEmpty()) val1 = l1Val.pop();
            else {
                val1 = l1Val.pop();
                val2 = l2Val.pop();
            }

            if (val1 + val2 + add >= 10){
                cur.val = val1 + val2 - 10 + add;
                add = 1;
            }
            else{
                cur.val = val1 + val2 + add;
                add = 0;
            }

            ListNode pre = new ListNode();
            pre.next = cur;
            cur = pre;
        }

        if (add == 1) {
            cur.val = 1;
            return cur;
        }
        else return cur.next;
    }
}

725. 分隔链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int N = getLength(root);
        ListNode[] result = new ListNode[k];

        ListNode cur = root;
        for (int i = 0; i < k; i++){
            if (cur != null) result[i] = cur;
            else result[i] = null;

            if (i < N%k){
                for (int j = 0; j < N/k; j++){
                    cur = cur.next;
                    if (cur == null) break;
                }
            }
            else{
                for (int j = 0; j < N/k - 1; j++){
                    cur = cur.next;
                    if (cur == null) break;
                }
            }

            if (cur != null){
                ListNode temp = cur.next;
                cur.next = null;
                cur = temp;
            }
        }

        return result;

    }

    int getLength(ListNode root){
        int l = 0;
        while (root != null){
            l++;
            root = root.next;
        }
        return l;
    }
}

328. 奇偶链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode odd = head, even = head.next, evenHead = head.next;

        while (even != null && even.next != null){
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        odd.next = evenHead;
        return head;
    }
}