这篇博客用于记录Fortune的LeetCode的刷题记录，基本每道题都包括了基础思路和follow up，我会尽力保障代码风格和充足注释的💪！

链表

删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：节点值顺次迁移，保存当前节点引用
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode lastNode = node;
        while (node.next != null) {
            lastNode = node;
            node.val = node.next.val;
            node = node.next;
        }
        lastNode.next = null;
    }
}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：下一节点的值前移并删除下一节点。
 * 时间复杂度：O(1);空间复杂度：O(1)
 */
class Solution {
    public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：先遍历获取长度，在遍历求值
 * 时间复杂度：O(n^2);空间复杂度：O(1)
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        if (head == null) {
            return 0;
        }
        int length = 0, result = 0;
        ListNode tmpHead = head;
        while(tmpHead != null) {
            length ++;
            tmpHead = tmpHead.next;
        }
        while(head != null) {
            result += head.val * pow2(--length);
            head = head.next;
        }
        return result;
    }

    public int pow2(int l) {
        int result = 1;
        for(int i = 0; i < l; i ++) {
            result *= 2;
        }
        return result;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：移位操作
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        if (head == null) {
            return 0;
        }
        int result = 0;
        while (head != null) {
            result = (result << 1) | head.val;
            head = head.next;
        }
        return result;
    }
}

返回倒数第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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：双指针
 * 时间复杂度： O(n);空间复杂度O(1)
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null) {
            return 0;
        }
        ListNode head2 = head;
        for (int i = 0; i < k - 1; i ++) {
            head = head.next;
        }
        while(head.next != null) {
            head = head.next;
            head2 = head2.next;
        }
        return head2.val;
    }
}

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：第一次遍历获取长度，第二次遍历逆序存入数组。
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        int lenght = 0;
        ListNode head2 = head;
        while (head != null) {
            lenght ++;
            head = head.next;
        }
        int[] result = new int[lenght];
        while (head2 != null) {
            result[--lenght] = head2.val;
            head2 = head2.next;
        }
        return result;
     }
}

/**
* 思路：利用栈
* 
*/
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        Stack<Integer> stack = new Stack<>();
        while(head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        int index = 0;
        while (!stack.isEmpty()) {
            result[index ++] = stack.pop();
        }
        return result;
     }
}

反转链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：双指针
 * 时间复杂度：O(n)
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode tmp = null;
        ListNode cur = null;
        ListNode pre = head;

        while (pre != null) {
            tmp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = tmp;
        }

        return cur;
    }
}

/**
 * 思路：双指针改写递归（从头开始反向）
 * 时间复杂度：O(n)
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseListRecursivr(head, null);
    }

    public ListNode reverseListRecursivr(ListNode head, ListNode pre) {
        if (head == null) {
            return pre;
        }
        ListNode tmp = head.next;
        head.next = pre;
        return reverseListRecursivr(tmp, head);
    }
}

/**
 * 思路：简洁递归(从尾开始反向)
 * 时间复杂度：O(n)
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode rtn = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return rtn;
    }
}

移除重复节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：暴力遍历
 * 时间复杂度：O(n^2);空间复杂度：O(1)
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return null;
        ListNode result = head;
        ListNode cur;
        while (head != null) {
            cur = head;
            while (cur.next != null) {
                if (cur.next.val == head.val) {
                    cur.next = cur.next.next;
                    
                } else {
                    cur = cur.next;
                }
            }
            head = head.next;
        }
        return result;
    }
}

/*
* 思路：哈希表
* 时间复杂度：O(n);空间复杂度：O(n)
*/
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return null;
        Set<Integer> exsited = new HashSet<>();
        exsited.add(head.val);

        ListNode result = head;
        while (head.next != null) {
            if (!exsited.add(head.next.val)) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return result;
    }
}

链表相交

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 * 思路：暴力遍历
 * 时间复杂度：O(m*n);空间复杂度：O(1)
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmp;
        while (headA != null) {
            tmp = headB;
            while (tmp != null) {
                if (headA == tmp) return headA;
                tmp = tmp.next;
            }
            headA = headA.next;
        }
        return null;
    }
}

/**
 * 思路：双指针相遇（两个指针遍历完各自链表后再从另一个链表头开始遍历，再交点相遇或者再次遍历到末尾null）
 * 时间复杂度：O(n + m);空间复杂度：O(1)
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode posA = headA;
        ListNode posB = headB;
        while (posA != posB) {
            if (posA == null) {
                posA = headB;
            } else {
                posA = posA.next;
            }
            if (posB == null) {
                posB = headA;
            } else {
                posB = posB.next;
            }
        }
        return posA;
    }
}

两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 * 思路：双指针相遇（两个指针遍历完各自链表后再从另一个链表头开始遍历，再交点相遇或者再次遍历到末尾null）各自去对方的轨迹里寻找，终会相遇♥
 * 时间复杂度：O(n + m);空间复杂度：O(1)
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode posA = headA;
        ListNode posB = headB;
        while (posA != posB) {
            if (posA == null) {
                posA = headB;
            } else {
                posA = posA.next;
            }
            if(posB == null) {
                posB = headA;
            } else {
                posB = posB.next;
            }  
        }
        return posA;
    }
}

/**
 * 思路：Hash法
 * 时间复杂度：O(n + m);空间复杂度：O(n)
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodes = new HashSet<>();
        while (headA != null) {
            nodes.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (nodes.add(headB)) {
                headB = headB.next;
            } else {
                return headB;
            }
        }
        return headB;
    }
}

合并两个升序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 * 思路：归并排序
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode pos = head;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                pos.next = l2;
                l2 = l2.next;
            } else {
                pos.next = l1;
                l1 = l1.next;
            }
            pos = pos.next;
        }
        pos.next = l1 == null ? l2 : l1;
        return head.next;
    }
}

/**
 * 思路：递归
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        if (l1.val >= l2.val) {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        } else {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
    }
}

删除给定值的链表节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：暴力遍历
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return head;
        ListNode result = head;
        while (head.val == val) {
            result = result.next;
            head = head.next;
        }
        while (head != null) {
            if (head.next != null && head.next.val == val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return result;
    }

删除排序链表的重复元素

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：暴力遍历，找当前节点的下一个不同值节点
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode result = head;
        ListNode tmp; //不要吝啬指针的使用！
        while (head != null) {
            tmp = head.next;
            while (tmp != null && tmp.val == head.val) {
                tmp = tmp.next;
            }
            head.next = tmp;
            head = head.next;
        }
        return result;
    }
}

判断链表是否有环

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 * 思路：哈希表，遍历判断是否出现重复节点
 * 时间复杂度：O(n);空间复杂度：O(n)
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.add(head)) {
                head = head.next;
            } else {
                return true;
            }
        }
        return false;
    }
}

/**
 * 思路：双指针
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

回文链表

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：利用栈，两次遍历
 * 时间复杂度： O(n);空间复杂度： O(n)
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        Stack<Integer> stack = new Stack<>();
        ListNode pos = head;
        while (pos != null) {
            stack.push(pos.val);
            pos = pos.next;
        }
        while (head != null) {
            if (head.val == stack.pop()) {
                head = head.next;
            } else {
                return false;
            }
        }
        return true;
    }
}


/**
 * 思路：双指针 + 反转链表（通过双指针遍历到链表中点，然后反转链表，再遍历比较）
 * 时间复杂度： O(n);空间复杂度： O(1)
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        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 cur = null;
        ListNode pre = slow;
        ListNode tmp = null;
        while (pre != null) {
            tmp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = tmp;
        }
        
        //遍历比较
        while (cur != null) {
            if (cur.val == head.val) {
                cur = cur.next;
                head = head.next;
            } else {
                return false;
            }
        }
        return true;
    }
}


/**
*
* 上述思路再优化：时间开销更小
*/
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode slow = head, fast = head, pre = null, tmp = null;
        while (fast != null && fast.next != null) {
            // 快慢指针找中点，并且同时翻转前半段链表
            fast = fast.next.next;
            tmp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = tmp;
        }
        if (fast != null) { 
            // 奇数节点链表慢指针后移一个
            slow = slow.next;
        }

        while (slow != null) {
            if (slow.val == pre.val) {
                slow = slow.next;
                pre = pre.next;
            } else {
                return false;
            }
        }
        return true;
    }
}

有序链表转换二叉搜索树

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 思路：递归（注意前半段链表的末尾要断开）
 * 时间复杂度：O(nlogn);空间复杂度：O(logn)--平衡二叉树的高度
 * 分析：主要的时间开销用于链表中间节点的查找
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        TreeNode mid = new TreeNode(slow.val);
        mid.left = sortedListToBST(head);
        mid.right = sortedListToBST(slow.next);
        return mid;
    }
}

/**
* 思路： 递归 + 链表转数组（空间换时间），节省了查找中点的时间开销
* 时间复杂度：O(n);空间复杂度：O(n+log(n)) = O(n)
*/
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int[] data = new int[20000];
        int length = 0;
        while (head != null) {
            data[length ++] = head.val;
            head = head.next;
        }
        return sortedArrayToBST(data, 0, (length - 1));
    }

    public TreeNode sortedArrayToBST(int[] data, int head, int tail) {
        if (head > tail) return null;
        TreeNode mid = new TreeNode(data[head + (tail - head) / 2]);
        mid.left = sortedArrayToBST(data, head, head +((tail - head) / 2 - 1);
        mid.right = sortedArrayToBST(data, head + (tail - head) / 2 + 1, tail);
        return mid;
    }
}



/**
* 思路：模拟二叉搜索树中序遍历
* 时间复杂度：O(n);空间复杂度：O(logn)
 */
class Solution {
    ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        int length = 0;
        this.head = head;
        while (head != null) {
            length ++;
            head = head.next;
        }
        return convertListToBST(0, length - 1);
    }

    public TreeNode convertListToBST(int left, int right) {
        if (left > right) return null;
        
        int mid = (right + left) / 2;

        TreeNode leftNode = convertListToBST(left, mid - 1);
        TreeNode midNode = new TreeNode(head.val);

        midNode.left = leftNode;

        head = head.next;

        TreeNode rightNode = convertListToBST(mid + 1, right);

        midNode.right = rightNode;

        return midNode;
    }
}

复杂链表的深拷贝

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。 

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
* 思路：利用两个List，根据引用获取原链表random对应索引，存储新链表的List也按索引顺次来连接
* 时间复杂度：O(n);空间复杂度：O(n)
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        List<Node> oldList = new ArrayList<>();
        List<Node> newList = new ArrayList<>();

        Node pos = head;
        while (pos != null) {
            oldList.add(pos);
            Node newNode = new Node(pos.val);
            newList.add(newNode);
            pos = pos.next;
        }
        oldList.add(null);
        newList.add(null);

        for(int i = 0; i < newList.size() - 1; i ++) {
            Node tmp = newList.get(i);
            tmp.next = newList.get(i + 1);       
            tmp.random = newList.get(oldList.indexOf(oldList.get(i).random));     
        } 
        
        return newList.get(0);
    }
}


/**
* 思路：HashMap
* 时间复杂度：O(n);空间复杂度：O(n)
*/
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node pos = head;
        while (pos != null) {
            Node newNode = new Node(pos.val);
            map.put(pos, newNode);
            pos = pos.next;
        }

        Node pos2 = head;
        while (pos2 != null) {
            Node newNode = map.get(pos2);
            newNode.next = pos2.next == null ? null : map.get(pos2.next);
            newNode.random = pos2.random == null ? null : map.get(pos2.random);
            pos2 = pos2.next;
        }
        return map.get(head);
    }
}

/*
* 思路：原地修改链表
* 时间复杂度：O(n);空间复杂度：O(1)
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node pos = head;

        while (pos != null) {
            Node newNode = new Node(pos.val);
            Node tmp = pos.next;
            pos.next = newNode;
            newNode.next = tmp;
            pos = tmp;
        }

        //这里注意不能同时修改next指针，会导致后续节点的random指向前置节点时，丢失旧节点对新节点的引用
        Node pos2 = head;
        while (pos2 != null) {
            Node newNode = pos2.next;
            newNode.random = pos2.random == null ? null : pos2.random.next;
            pos2 = newNode.next;
        }

        Node pos3 = head;
        Node result = head.next;
        Node pos4 = head.next;
        while (pos3 != null) {
            pos3.next = pos3.next.next;
            pos3 = pos3.next;
            pos4.next = pos4.next == null ? null : pos4.next.next;
            pos4 = pos4.next; 
        }
        return result;
    }
}

链表的插入排序

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：通过两个指针维护已排序部分的链表，遍历查找插入点，插入点为头尾的特殊考虑
 * 时间复杂度：O(n^2);空间复杂度：O(n)
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;
        ListNode sortedTail = head;
        ListNode ptr = head.next;
        while (ptr != null) {
            ListNode cur = head;
            ListNode pre = null;
            while (pre != sortedTail && cur.val < ptr.val) {
                pre = cur;
                cur = cur.next;
            }
            if (pre == null) {
                sortedTail.next = ptr.next;
                ptr.next = head;
                head = ptr;
            } else if (pre == sortedTail) {
                sortedTail = ptr;
            } else {
                sortedTail.next = ptr.next;
                ptr.next = cur;
                pre.next = ptr;
            } 
            ptr = sortedTail.next;
        } 
        return head;
    }
}

/**
* 简单优化一下思路：在已排序部分头尾插入时不再遍历一遍找插入点，直接通过比较确认插入点
*/
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;
        ListNode sortedTail = head;
        ListNode ptr = head.next;
        while (ptr != null) {
            if (ptr.val <= head.val) {
                sortedTail.next = ptr.next;
                ptr.next = head;
                head = ptr;
            } else if (ptr.val >= sortedTail.val) {
                sortedTail = ptr;
            } else {
                ListNode cur = head;
                ListNode pre = null;
                while (pre != sortedTail && cur.val < ptr.val) {
                    pre = cur;
                    cur = cur.next;
                }
                sortedTail.next = ptr.next;
                ptr.next = cur;
                pre.next = ptr;
            }
            ptr = sortedTail.next;
        } 
        return head;
    }
}

分割链表

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

1
2
3
示例
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：维护左侧较小值链表，先遍历找到右侧链表头，再从右侧链表头开始遍历找属于左侧链表的节点。
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode leftHead = null, leftPtr = null;
        while (head != null && head.val < x){
            if (leftHead == null) {
                leftHead = head;
                leftPtr = leftHead;
            } else {
                leftPtr.next = head;
                leftPtr = leftPtr.next;
            }
            head = head.next;
        }

        ListNode rightPtr = head;
        while (rightPtr != null) {
            if (rightPtr.next != null && rightPtr.next.val < x) {
                if (leftHead == null) {
                    leftHead = rightPtr.next;
                    leftPtr = leftHead;
                } else {
                    leftPtr.next = rightPtr.next;
                    leftPtr = leftPtr.next;
                }
                rightPtr.next = rightPtr.next.next;
            } else {
                rightPtr = rightPtr.next;
            }
        }
        if (leftHead == null) {
            return head;
        } else {
            leftPtr.next = head;
            return leftHead;
        } 
    }
}


// more lint code 
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode leftHead = new ListNode(0), rightHead = new ListNode(0);
        ListNode leftTail = leftHead, rightTail = rightHead;
        while (head != null) {
            if (head.val < x) {
                leftTail.next = head;
                leftTail = leftTail.next;
            } else {
                rightTail.next = head;
                rightTail = rightTail.next;
            }
            head = head.next;
        }
        rightTail.next = null; //右侧链表末尾要断开
        leftTail.next = rightHead.next;
        return leftHead.next;
        
    }
}

奇偶链表

按链表节点的索引的奇偶分割链表

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
/**
* 思路：分别维护左右侧链表的头尾指针，顺次从末尾插入
* 时间复杂度：O(n);空间复杂度：O(1)
*/
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode evenHead = new ListNode(0), oddHead = new ListNode(0);
        ListNode evenTail = evenHead, oddTail = oddHead;
        int index = 1;
        while (head != null) {
            if (index % 2 == 0) {
                evenTail.next = head;
                evenTail = evenTail.next;
            } else {
                oddTail.next = head;
                oddTail = oddTail.next;
            }
            head = head.next;
            index ++;
        }
        evenTail.next = null; //右侧末尾检点的next要断开！
        oddTail.next = evenHead.next;
        return oddHead.next;
    }
}

链表组件

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。

同时给定列表 G，该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：暴力遍历，利用List顺序存储G中值对应的数组中的index，通过index判断在链表中是否连续
 * 时间复杂度：O(n^2)考虑List的indexOf以及remove等操作；空间复杂度：O(n + k)
 */
class Solution {
    public int numComponents(ListNode head, int[] G) {
        if (head == null || G.length == 0) return 0;

        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        List<Integer> listForIndex = new ArrayList<>();
        for (int i = 0; i < G.length; i++) {
            listForIndex.add(list.indexOf(G[i]));
        }
        
        int count = 0;
        while (listForIndex.size() > 0) {
            int index = Collections.min(listForIndex);
            listForIndex.remove(listForIndex.indexOf(index));
            while (listForIndex.indexOf(++index) >= 0) {
                listForIndex.remove(listForIndex.indexOf(index));
            }
            count++;
        }
        return count;
    }
}


/**
* 思路：上一种解法为遍历G，判断G中的元素能不能构成连续链表；当前思路为线性遍历链表，判断连续链表是否在G中。
* 时间复杂度：O(n + k); 复杂度：O(k)
*/
class Solution {
    public int numComponents(ListNode head, int[] G) {
        if (head == null || G.length == 0) return 0;

        int count  = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < G.length; i++) {
            set.add(G[i]);
        }
        while (head != null) {
            if (set.contains(head.val)) {
                ListNode componentHead = head;
                while (componentHead != null && set.contains(componentHead.val)) {
                    componentHead = componentHead.next;
                }
                count ++;
                head = componentHead;
            } else {
                head = head.next;
            }
            
        }
        return count;
    }
}

两两交换链表节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：三指针迭代
 * 时间复杂度：O(n); 空间复杂度：O(1)
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode result = head.next;
        ListNode pre = null;
        while (head != null && head.next != null) {
            ListNode cur = head;
            ListNode post = head.next;

            cur.next = post.next;
            post.next = cur;

            if (pre != null) {
                pre.next = post;
            }

            pre = cur;
            head = cur.next;  
        }
        return result;
    }
}

/**
* 思路：递归
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode firstNode = head;
        ListNode secondNode = head.next;

        firstNode.next = swapPairs(secondNode.next);
        secondNode.next = firstNode;

        return secondNode;
    }
}

排序链表

在 O(n * logn) 时间复杂度和O(1)空间复杂度下，对链表进行排序。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：自底向上的归并排序
 * 时间复杂度：O(nlogn);空间复杂度：O(1)
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        int range = 1;
        int length = 0;

        ListNode ptr = head;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode dummyPtr = dummy; // dummyPtr需要始终指向“一次”归并结果的末尾节点

        while (range < length) {
            // 一层归并开始（range = 1、2、4...）
            ListNode head1 = dummy.next;
            while (head1 != null) {
                // 一次归并开始
                ListNode head2 = head1;
                int lengthOfHead1 = 0;
                
                for (int i = 0; i < range; i++) {
                    if (head2 == null) break;// 处理剩余链表长度不足range
                    head2 = head2.next;
                    lengthOfHead1 ++;
                }
                
                // 计算一次归并的后半段链表的长度并保存下一次归并的head1引用
                ListNode nextHead1 = head2;
                int lengthOfHead2 = 0;
                for (int i = 0; i < range; i++) {
                    if (nextHead1 == null) break;
                    nextHead1 = nextHead1.next;
                    lengthOfHead2 ++;
                } 
				// 归并排序的具体处理：利用index来辅助进行当前归并的两段链表是否到末尾	
                for (int i = 0, index1 = 0, index2 = 0; i < (lengthOfHead1 + lengthOfHead2); i++) {
                    if (index1 >= lengthOfHead1) {
                        dummyPtr.next = head2;
                        head2 = head2.next;
                        index2 ++;
                    } else if (index2 >= lengthOfHead2) {
                        dummyPtr.next = head1;
                        head1 = head1.next;
                        index1 ++;
                    } else if (head1.val <= head2.val) {
                        dummyPtr.next = head1;
                        head1 = head1.next;
                        index1 ++;
                    } else {
                        dummyPtr.next = head2;
                        head2 = head2.next;
                        index2 ++;
                    }
                    dummyPtr = dummyPtr.next;
                }
                head1 = nextHead1;
            }
            dummyPtr.next = null; // 一层归并结束时，末尾节点需要置空
            dummyPtr = dummy; //一层归并结束，dummyPtr重置
            range *= 2;
        }
        return dummy.next;
    }
}


/**
* 思路：递归归并排序
* 时间复杂度：O(nlogn);空间复杂度：O(logn)
*/
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head, slow = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        ListNode head1 = sortList(head);
        ListNode head2 = sortList(slow);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                cur.next = head1;
                head1 = head1.next;
                cur = cur.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
                cur = cur.next;
            }
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }

}

/**
* 思路：递归快排
* 时间复杂度：O();空间复杂度：O()
*/
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
       	ListNode ptr1 = dummy1, ptr2 = dummy2, ptr = head.next;
        while (ptr != null) {
            if (ptr.val <= head.val) {
                ptr1.next = ptr;
                ptr1 = ptr1.next;
            } else {
                ptr2.next = ptr;
                ptr2 = ptr2.next;
            }
            ptr = ptr.next;
        }
        ptr1.next = null;
        ptr2.next = null;
        dummy1.next = sortList(dummy1.next);
        dummy2.next = sortList(dummy2.next);
        ptr1 = dummy1;
        while (ptr1.next != null) {
            ptr1 = ptr1.next;
        }
        ptr1.next = head;
        head.next = dummy2.next;
        return dummy1.next;
    }
}

链表相加

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

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
74
75
76
77
78
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：反转链表 + 头插法
 * 时间复杂度：O(n);空间复杂度：O(n)
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode res = null;

        l1 = reverseList(l1);
        l2 = reverseList(l2);

        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            sum += l1 == null ? 0 : l1.val;
            sum += l2 == null ? 0 : l2.val;
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = res;
            res = newNode;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }

        return res;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
}

/**
* 如果要求不破化原链表结构：利用栈
* 时间复杂度：O(n);空间复杂度：O(n)
*/
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = null;

        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        } 
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
            int sum = carry;
            sum += s1.isEmpty() ? 0 : s1.pop();
            sum += s2.isEmpty() ? 0 : s2.pop();
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = res;
            res = newNode;
        }
        return res;
    }
}

链表重排

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-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
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：快慢指针找中点 + 反转链表
 * 时间复杂度：O(n);空间复杂度：O(1)
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
		
        if (pre != null) pre.next = null;

        slow = reverseList(slow);

        ListNode dummy = new ListNode(0);
        ListNode ptr = dummy;
        while (head != null) {
            // 这里需要注意ptr.next指向slow之前需要将head指向head.next
            ptr.next = head;
            ptr = ptr.next;
            head = head.next;
            ptr.next = slow;
            ptr = ptr.next;
            slow = slow.next;
        }
        ptr.next = slow == null ? null : slow;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
}

下一个更大的节点

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：暴力遍历
 * 时间复杂度：O(n^2); 空间复杂度：O(1)
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        if (head == null) {
            return new int[]{};
        }
        int length = 0;
        ListNode ptr = head;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }
        int[] result = new int[length];
        int index = 0;

        while (head != null) {
            ListNode cur = head;
            while (cur != null && cur.val <= head.val) {
                cur = cur.next;
            }
            result[index++] = cur == null ? 0 : cur.val;
            head = head.next;
        }

        return result;
    }
}

/**
 * 思路：单调栈（单调递增栈：出栈顺序递增）栈中存储的是节点下标
 * 时间复杂度：O(n); 空间复杂度：O(n)
 */

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        int[] result = new int[list.size()];
        //栈里面保存的是下标
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < list.size(); i++) {
            while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
                //出栈
                result[stack.pop()] = list.get(i);
            }
            stack.push(i);
        }
        //递减栈中的元素全部归零
        while (!stack.empty()){
            result[stack.pop()] = 0;
        }
        return result;
    }
}

/**
* 思路：单调栈（单调递增栈） 栈中存储节点值 链表从右向左遍历
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        if (head == null) {
            return new int[]{};
        }
        
        List<Integer> list = new ArrayList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int[] result = new int[list.size()];
        Stack<Integer> stack = new Stack<>();
		
        // 从右向左遍历
        for (int i = list.size() - 1; i >= 0; i--) {
            // 找到当前节点右侧（在当前节点之前遍历）的最后进栈的（最靠近当前节点的）大于当前节点的节点
            while (!stack.isEmpty() && stack.peek() <= list.get(i)) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(list.get(i));
        }

        return result;
    }
}

分隔链表

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
74
75
76
77
78
79
80
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：链表长度 / k = 每组个数，链表长度 % k = 需要额外分配一个节点的组数
 * 时间复杂度：O(n + k); 空间复杂度：O(k)
 */
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] lists = new ListNode[k];
        
        ListNode ptr = root;
        int length = 0;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }
        
        int numOfPart = length / k;
        int numOfPlusOne = length % k;

        int index;
        for (index = 0; index < numOfPlusOne; index++) {
            lists[index] = root;
            ListNode pre = null;
            for (int i = 0; i <= numOfPart; i++) {
                pre = root;
                root = root.next;
            }
            pre.next = null;
        }
        while (root != null) {
            lists[index++] = root;
            ListNode pre = null;
            for (int i = 0; i < numOfPart; i++) {
                if (root == null) break;
                pre = root;
                root = root.next;
            }
            pre.next = null;    
        }
        for (index = index; index < k; index ++) {
            lists[index] = null;
        }
        return lists;
    }
}

// more lint code 
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] lists = new ListNode[k];

        ListNode ptr = root;
        int length = 0;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }
        
        int width = length / k;
        int remainer = length % k;

        for (int i = 0; i < k; i ++) {
            lists[i] = root;
            if (root == null) continue;
            ListNode pre = null;
            for (int j = 0; j < (remainer > 0 ? width + 1 : width); j ++){
                pre = root;
                root = root.next;
            }
            remainer--;
            pre.next = null;
        }
        return lists;
    }
}

环形链表

找到环形链表的第一个入环节点

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 * 思路：哈希表
 * 时间复杂度：O(n); 空间复杂度：O(n)
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return head;
            }
            head = head.next;
        }
        return null;
    }
}

/**
* 思路：快慢指针：先判断有无环，再找入环点（入环点思路见下图）
* 时间复杂度：O(n); 空间复杂度：O(1)
*/

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode inteact = getInteractNode(head);
        if (inteact == null) {
            return null;
        } else {
            ListNode res = head;
            while (res != inteact) {
                inteact = inteact.next;
                res = res.next;
            }
            return res;
        }
    }

    public ListNode getInteractNode(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return fast;
            }
        }
        return null;
    }
}

反转链表II

反转从链表从 m-n 的节点（要求一趟扫描完成）

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
/** 
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：双指针
 * 时间复杂度：O(n); 空间复杂度：O(1)
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;

        int index = 1;
        ListNode pre = null, cur = head;
        
        while (index < m) {
            pre = cur;
            cur = cur.next;
            index ++;
        }

        ListNode reversPre = null, reverseCur = cur, tmp = null;
        while (index <= n) {
            tmp = reverseCur.next;
            reverseCur.next = reversPre;
            reversPre = reverseCur;
            reverseCur = tmp;
            index ++;
        }

        if (pre != null) {
            pre.next = reversPre;
        } else {
            // 注意处理一下从头开始反转的情况
            head = reversPre;
        }
        
        cur.next = reverseCur;
        return head;
    }
}

/**
* 思路：递归
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        } else {
            ListNode res = reverseBetween(head.next, m - 1, n - 1);
            head.next = res;
            return head;
        }
    }

    // 递归反转前N个节点，在递归反转单链表的基础上，在递归结束条件处记录了每层递归中，尾部节点需要指向的下一节点post
    ListNode post = null;
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            post = head.next;
            return head;
        }

        ListNode res = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = post; // 在递归反转整体链表中，这里为head.next = null;
        return res;
    }
}

扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

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
/*
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
* 思路：递归，类似二叉树的前序遍历
* 时间复杂度：O(n)：每个节点访问一次; 空间复杂度：O(n): 看作二叉树的话，其不一定是平衡二叉树
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
        Node nextNode = flatten(head.next);
        Node childNode = flatten(head.child);
        if (childNode == null) {
            head.next = nextNode;
            if (nextNode != null) {
                nextNode.prev = head;
            }    
        } else {
            head.next = childNode;
            childNode.prev = head;
            while (childNode.next != null) {
                childNode = childNode.next;
            }
            childNode.next = nextNode;
            if (nextNode != null) {
                nextNode.prev = childNode;
            } 
            head.child = null; // 注意前置节点的child要置空
        }
        return head;
    }
}

/**
* 思路：利用栈进行迭代
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
       	// 由于需要处理next、pre指针，所以相较于二叉树的前序遍历，需要一个pre指针来保存前序节点
        Node pre = null, cur = head; 

        Stack<Node> stack = new Stack<>();
        stack.push(head);

        while (!stack.isEmpty()) {
            cur = stack.pop();
            if (pre != null) {
                // 处理头节点：没有前序节点
                pre.next = cur;
            }
            cur.prev = pre;
            if (cur.next != null) {
                stack.push(cur.next);
            }
            if (cur.child != null) {
                stack.push(cur.child);
                cur.child = null;
            }
            pre = cur;
        }

        return head;
    }
}

删除排序链表中的重复节点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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：双指针一遍扫描链表，由于重复节点需要全部删除，所以需要维护一个当前指针的前置指针
 * 时间复杂度：O(n); 空间复杂度：O(1)
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode cur = head, pre = null;
        while (cur != null) {
            // find next diff node
            ListNode ptr = cur;
            int count = 0;
            while (ptr != null && ptr.val == cur.val) {
                count ++;
                ptr = ptr.next;
            }
            if (count > 1) {
                if (pre == null) {
                    head = ptr;
                } else {
                    pre.next = ptr;
                }
            } else {
                pre = cur;
            }
            cur = ptr;
        }
        return head;
    }
}

/**
* 思路：递归
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head；	
       
        if (head.val != head.next.val) {
            // 当前头部没有重复节点
            head.next = deleteDuplicates(head.next);
        } else {
            // 处理头部重复节点
            ListNode nextNode = head;
            while (nextNode != null && nextNode.val == head.val) {
                nextNode = nextNode.next;
            } 
            head = deleteDuplicates(nextNode);
        }
        return head;
    }
}

链表相加

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：一遍扫描即可，主要需要关注一下while循环结束的条件写法，代码比较简洁易读
 * 时间复杂度：O(n); 空间复杂度：O(n)
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode ptr = dummy;
        int plus = 0;
        while (l1 != null || l2 != null || plus != 0) {
            int sum = 0;
            sum += l1 == null ? 0 : l1.val;
            sum += l2 == null ? 0 : l2.val;
            l1 = l1 == null ? null :l1.next;
            l2 = l2 == null ? null : l2.next;
            int cur = (sum + plus) % 10;
            plus = (sum + plus) / 10;
            ptr.next = new ListNode(cur);
            ptr = ptr.next;
        }
        return dummy.next;
    }
}

删除链表中连续和为0的节点

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：递归
 * 时间复杂度：O(n^2); 空间复杂度：O(n)
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        if (head == null) return null;

        ListNode next = removeZeroSumSublists(head.next);

        // 添加当前head后查找值为0的连续序列
        ListNode cur = next;
        int sum = head.val;
        while (cur != null && sum != 0) {
            sum += cur.val;
            cur = cur.next;
        }

        if (sum == 0) {
            head = cur;
        } else {
            head.next = next;
        }

        return head;

    }
}

/**
* 思路：HashMap！
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0); // 将头节点纳入处理范围
        dummy.next = head;
        Map<Integer, ListNode> map = new HashMap<>();

        int sum = 0;
        ListNode ptr1 = dummy;
        while (ptr1 != null) {
            // 第一遍遍历添加<当前节点sum, 节点>到map
            // 后续节点相同的sum会覆盖当前节点
            sum += ptr1.val;
            map.put(sum, ptr1);
            ptr1 = ptr1.next;
        }
        sum = 0;
        ListNode ptr2 = dummy;
        while (ptr2 != null) {
            // 第二遍遍历，可以根据map找到sum值为当前sum的最后一个节点
            // 说明当前节点和找到的节点之间所有节点和为0，删除该所有区间节点
            sum += ptr2.val;
            ptr2.next = map.get(sum).next;
            ptr2 = ptr2.next;
        }

        return dummy.next;
        
    }
}

二叉树中的链表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
* 思路：递归遍历二叉树，每个树节点再递归遍历和链表进行比较
* 时间复杂度：O(n * k); 空间复杂度：O(n * k) n fot Tree, k for List
*/
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        return isPath(head, root) || (isSubPath(head, root.left) || isSubPath(head, root.right));
    }

    public boolean isPath(ListNode head, TreeNode root) {
        if (head == null) return true;
        if (root == null) return false;
        return head.val == root.val && (isPath(head.next, root.left) || isPath(head.next, root.right));
    }
}

删除链表倒数第N个节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：双指针找倒数第N个节点
 * 时间复杂度：O(n); 空间复杂度：O(1)
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        ListNode fast = head, slow = head, pre = null;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            pre = slow;
            fast = fast.next;
            slow = slow.next;
        }
        if (pre == null) {
            head = head.next;
        } else {
            pre.next = slow.next;
        }
        return head;
    }
}

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 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
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：快慢指针一遍扫描，获取倒数第remain个节点
 * 时间复杂度：O(n); 空间复杂度：O(1)
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;

        int length = 0;
        ListNode ptr = head;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }
        int remain = k % length;

        if (remain == 0) return head;

        ListNode fast = head, slow = head, pre = null;
        for (int i = 0; i < remain; i++) {
            fast = fast.next;
        }

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

        pre.next = null;
        ListNode newHead = slow;
        while (slow != null) {
            pre = slow;
            slow = slow.next;
        }
        pre.next = head;
        return newHead;

    }
}

/**
* 思路：先成环，旋转后的头节点需要向前移动length - (k % length)步
* 时间复杂度：O(n); 空间复杂度：O(1)
*/
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length ++;
        } 
        tail.next = head;

        int step = length - (k % length) - 1;
        for (int i = 0; i < step; i++) {
            head = head.next;
        }

        ListNode res = head.next;
        head.next = null;
        return res;
    }
}

K个一组翻转链表

要求空间复杂度为O(1)

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
74
75
76
77
/**
* 思路：递归
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) return head; 

      	// 当前头节点向后是否足K
        ListNode tail = head;
        int length = 1;
        while (tail != null && length < k) {
            tail = tail.next;
            length ++;
        }

      	// 不足k直接返回当前头节点不翻转
        if (tail == null) return head;

      	// 足k则先翻转后续链表
        ListNode nextHead = reverseKGroup(tail.next, k);
      
      	// 翻转当前链表组
        ListNode pre = null, cur = head, tmp = null;
        while (pre != tail) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
      
      	// 和后续已翻转好的链表组合
        head.next = nextHead;
      
      	// 返回翻转后的头节点
        return tail;
    }
}

/**
 * 思路：先计算长度，翻转length/k组，每组翻转前需要存储该组翻转后的尾节点用于指向下一组翻转后的头节点
 * 时间复杂度：O(n); 空间复杂度：O(1)
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) return head; 

      	
        int length = 0;
        ListNode ptr = head;
        while (ptr != null) {
            length ++;
            ptr = ptr.next;
        }
        int numOfParts = length / k;

      	// dummy节点用于避免头节点处的特判，简化代码
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy, kPre = dummy, cur = head, tmp = null;
        for (int i = 0; i < numOfParts; i++) {
            ListNode futureTail = cur;
            for (int j = 0; j < k; j++) {
                tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            kPre.next = pre;
            kPre = futureTail;
        }
        if (kPre != null) kPre.next = cur;
        return dummy.next;
    }
}

合并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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 * 思路：递归 -> 也可改写为迭代，时间复杂度一样，空间复杂度为O(1)
 * 时间复杂度：O(n*k^2); 空间复杂度：o(k) n为链表长度
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> list = new ArrayList<>();
        for (ListNode head : lists) {
            list.add(head);
        }
        return recursiveMergeKLists(list);
    }

    public ListNode recursiveMergeKLists(List<ListNode> lists) {
        if (lists.size() == 0) return null;

        ListNode currentHead = lists.get(0);
        lists.remove(0);
        ListNode sortedHead = recursiveMergeKLists(lists);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (currentHead != null && sortedHead != null) {
            if (currentHead.val <= sortedHead.val) {
                cur.next = currentHead;
                currentHead = currentHead.next;
            } else {
                cur.next = sortedHead;
                sortedHead = sortedHead.next;
            }
            cur = cur.next;
        }
        cur.next = currentHead != null ? currentHead : sortedHead;
        return dummy.next;
    }
}

/**
* 思路：多路归并
* 时间复杂度：O(kn*logk); 空间复杂度：O(logk)
*/
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return recursiveMergeKLists(lists, 0, lists.length - 1);
    }

    public ListNode recursiveMergeKLists(ListNode[] lists, int l , int r) {
        if (l == r) return lists[l];
        if (l > r) return null;
        int mid = (l + r) / 2;
        ListNode leftHead = recursiveMergeKLists(lists, l , mid);
        ListNode rightHead = recursiveMergeKLists(lists, mid + 1, r);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (leftHead != null && rightHead != null) {
            if (leftHead.val <= rightHead.val) {
                cur.next = leftHead;
                leftHead = leftHead.next;
            } else {
                cur.next = rightHead;
                rightHead = rightHead.next;
            }
            cur = cur.next;
        }
        cur.next = leftHead != null ? leftHead : rightHead;
        return dummy.next;
    }
}

/**
* 思路：最小堆
* 时间复杂度：O(kn*logk); 空间复杂度：O(k)
*/
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (ListNode o1, ListNode o2) -> (o1.val - o2.val));
        for (ListNode head : lists) {
            if (head == null) continue;
            queue.add(head);
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if (cur.next != null) queue.add(cur.next);
        }
        return dummy.next;
    }
}

单调栈

柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

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
/**
* 思路：暴力遍历寻找左右两侧最近的更矮柱子
* 时间复杂度：O(n); 空间复杂度：O(1) 
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int left = i, right = i;
            while (left >= 0 && heights[left] >= height) {
                left --;
            }
            while (right <= heights.length - 1 && heights[right] >= height) {
                right ++;
            }
            area = Math.max(area, height * (right - left - 1));
        }
        return area;
    }
}

/**
* 思路：单调栈（单调递减栈）：通过单调递减栈保障栈中每个元素的下一个元素为其左边最近的更小元素
* 每次压栈时，如果大于等于栈顶元素则直接压栈；否则弹出栈中所有比该元素大的元素，该元素为这些弹出元素右边最近的更小元素
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        int area = 0;
        // 为了简化代码，在数组头尾各插入一个0（保障左右两侧一定有更小元素）
        int[] copyHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, copyHeights, 1, heights.length);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < copyHeights.length; i++) {
             while (!stack.isEmpty() && copyHeights[stack.peek()] > copyHeights[i]) {
                 int height = copyHeights[stack.pop()];
                 int width = i - stack.peek() - 1;
                 area = Math.max(area, height * width);
             }
             stack.push(i);
        }
        return area;
    }
}

接雨水

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

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
74
75
76
77
78
79
/**
* 思路：暴力遍历
* 时间复杂度：O(n^2); 空间复杂度：O(1)
*/
class Solution {
    public int trap(int[] height) {
        int volumn = 0;
        for (int i = 0; i < height.length; i++) {
            int leftMax = height[i], rightMax = height[i];
          	// 遍历找到左侧和右侧最高的柱子
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = i; j < height.length; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
          	// 当前柱子能接雨水的最高高度为两侧最高柱子的较小值
            int curHeight = rightMax > leftMax ? (leftMax - height[i]) : (rightMax - height[i]);
            volumn += curHeight;
        }
        return volumn;
    }
}

/**
* 思路：单调递增栈，通过单调栈来定位每根柱子左右两侧最近的更高柱子，定位当前柱子高度为底可以储水的最长横向条形块
* 时间复杂度：O(n); 空间复杂度：O(n)
*/
class Solution {
    public int trap(int[] height) {
        int volumn = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int curHeight = height[stack.pop()];
                if (stack.isEmpty()) break;
                int width = i - stack.peek() - 1;
                int boundHeight = Math.min(height[i], height[stack.peek()]);
                volumn += width * (boundHeight - curHeight);
            }
            stack.push(i);
        }
        return volumn;
    }
}

/**
* 思路：双指针right & left对向遍历，分别维护leftMax和rightMax。
* 对于left来讲，leftMax可信；对于right来讲，rightMax可信呢。
* 由于每根柱子的最高储水量为min(leftMax, rightMax)
* 所以当leftMax < rightMax时，即使left指针的rightMax不可信，但是最高储水量就可以确定为leftMax
* 时间复杂度：O(n); 空间复杂度：O(1)
*/
class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int rightMax = 0, leftMax = 0;
        int volumn = 0;
        while (left <= right) {
            if (leftMax < rightMax) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    volumn += (leftMax - height[left]);
                }
                left ++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    volumn += (rightMax - height[right]);
                }
                right --;
            }
        }
        return volumn;
    }
}