Leetcode题解 - 链表

Posted on | Post modified: | In
Words count in article: 6.6k

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站， 刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是链表相关题目题解总结。

[TOC]

链表

2. 两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路

设置哨兵节点，每次新建节点保存当前位的值，并将进位给下一次迭代用。

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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        cur = dummy
        plus = 0
        
        while l1 or l2 or plus:
            if l1:
                plus += l1.val
                l1 = l1.next
            if l2:
                plus += l2.val
                l2 = l2.next
            cur.next = ListNode(plus%10)
            plus //= 10
            cur = cur.next
            
        return dummy.next

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

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

解题思路

新建伪结点，先让原指针走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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head or n < 0:
            return None
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        for i in range(n):
            head = head.next
            
        while head:
            head = head.next
            pre = pre.next
        
        pre.next = pre.next.next
        
        return dummy.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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    public String toString() {
        return "ListNode [val=" + val + "]";
    }
}
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        for (int i = 0; i < n; i++){
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;

    }
}
public class Main {

    public static void main(String[] args) {
        ListNode ln1= new ListNode(1);
        ListNode ln2= new ListNode(2);
        ListNode ln3= new ListNode(3);
        ListNode ln4= new ListNode(4);
        ListNode ln5= new ListNode(5);
        ln1.next=ln2;
        ln2.next=ln3;
        ln3.next=ln4;
        ln4.next=ln5;
        ln5.next=null;
        Solution sol = new Solution();
        ListNode res = sol.removeNthFromEnd(ln1, 2);
        while (res!=null) {
            System.out.println(res.toString());
            res = res.next;
        }
    }
}

21. 合并两个有序链表

题目描述

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

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        
        dummy = ListNode(0)
        pre = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                pre.next = ListNode(l1.val)
                l1 = l1.next
            else:
                pre.next = ListNode(l2.val)
                l2 = l2.next
            pre = pre.next
        
        pre.next = l1 if l1 else l2
    
        return dummy.next

23. 合并K个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路

分治+归并

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:len(lists)//2])
        right = self.mergeKLists(lists[len(lists)//2:])
        return self.merge(left, right)
    
    def merge(self, left, right):
        if not left:
            return right
        if not right:
            return left
        dummy = ListNode(0)
        pre = dummy
        while left and right:
            if left.val < right.val:
                pre.next = left
                left = left.next
            else:
                pre.next = right
                right = right.next
            pre = pre.next
        pre.next = left if left else right
        
        return dummy.next

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

题目描述

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

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路

设置头节点，向后遍历。

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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        while pre.next and pre.next.next:
            cur = pre.next
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre.next.next = cur
            pre = pre.next.next
        
        return dummy.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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    public String toString() {
        return "ListNode [val=" + val + "]";
    }
}
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head==null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while (pre!=null && pre.next!=null && pre.next.next!=null){
            ListNode Node = new ListNode(pre.next.val);
            Node.next = pre.next.next.next;
            pre.next = pre.next.next;
            pre.next.next = Node;
            pre = pre.next.next;
        }
        return dummy.next;
    }
}
public class Main {

    public static void main(String[] args) {
        ListNode ln1= new ListNode(1);
        ListNode ln2= new ListNode(2);
        ListNode ln3= new ListNode(3);
        ListNode ln4= new ListNode(4);
        ListNode ln5= new ListNode(5);
        ln1.next=ln2;
        ln2.next=ln3;
        ln3.next=ln4;
        ln4.next=ln5;
        ln5.next=null;
        Solution sol = new Solution();
        ListNode res = sol.swapPairs(ln1);
        while (res!=null) {
            System.out.println(res.toString());
            res = res.next;
        }
    }
}

25. K 个一组翻转链表

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

1
2
3
4
5
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路

求出翻转的次数+对每一次进行反转

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        
        
        if not head or not head.next or k <= 1:
            return head
        
        length = 0
        pre = head
        while pre:
            length += 1
            pre = pre.next
        
        cycle = length // k
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        for i in range(cycle):
            start, end = i*k, (i+1)*k-1
            
            cur = pre.next
            for i in range(start, end):
                temp = cur.next
                cur.next = temp.next
                temp.next = pre.next
                pre.next = temp
                
            for i in range(k):
                pre = pre.next
        
        return dummy.next

61. 旋转链表

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

1
2
3
4
5
6
7
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解题思路

先求链表长度，当k>length时，k对length求余，然后将链表后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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        length = 0
        cur = head
        while cur:
            cur = cur.next
            length += 1
        
        k = k % length
        if k == 0:
            return head
        
        fast, slow = head, head
        for i in range(k):
            fast = fast.next
            
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        temp = slow.next
        slow.next = None
        fast.next = head

        # temp 就是结果，直接返回也可
        head = temp
        
        return head

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

题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

1
2
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

1
2
输入: 1->1->1->2->3
输出: 2->3

解题思路

要删除重复的节点，而头节点就有可能是重复的节点，因此新建头节点，同样的值略过。

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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        while head and head.next:
            if head.val != head.next.val:
                head = head.next
                pre = pre.next
            else:
                val = head.val
                while head and head.val == val:
                    head = head.next
                pre.next = head
        
        return dummy.next

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

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

1
2
输入: 1->1->2->3->3
输出: 1->2->3

解题思路

每次迭代判断当前节点和下一节点是否相等，若相等，该节点的下个节点等于下个节点的下个节点，相当于下个节点和当前节点相等，就跳过下个节点。

当当前节点和下一节点不相等时，当前节点往前走，判断下一节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
                
        return head

86. 分隔链表

题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解题思路

用两个指针，分别保存比x小的及比x大的值，对原链表进行遍历根据值的大小拼接在相应的链表后面，最后在把两个链表拼接在一起就可以了。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        pre = dummy
        larger = ListNode(0)
        temp = larger
        
        while head:
            if head.val < x:
                pre.next = head
                pre = pre.next
            else:
                node = ListNode(head.val)
                temp.next = node
                temp = temp.next
            head = head.next
            
        pre.next = larger.next
        return dummy.next

92. 反转链表 II

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        count = 1
        while pre.next and count < m:
            pre = pre.next
            count += 1
        
        if count < m:
            return head
        
        mNode = pre.next
        cur = mNode.next
        
        while cur and count < n:
            Next = cur.next
            cur.next = pre.next
            pre.next = cur
            mNode.next = Next
            cur = Next
            count += 1
            
        return dummy.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
26
27
28
29
30
31
32
33
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        for i in range(m-1):
            pre = pre.next
        
        cur = pre.next
        
        for i in range(n-m):
            temp = cur.next
            cur.next = temp.next
            temp.next = pre.next
            pre.next = temp
        
        return dummy.next

109. 有序链表转换二叉搜索树

题目描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解题思路

将链表转换为数组，然后构建二叉搜索树。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return None
        
        array = []
        while head:
            array.append(head.val)
            head = head.next
        
        return self.helper(array)
    
    def helper(self, array):
        if len(array) == 0:
            return None
        mid = len(array)//2
        root = TreeNode(array[mid])
        root.left = self.helper(array[:mid])
        root.right = self.helper(array[mid+1:])
        return root

138. 复制带随机指针的链表

题目描述

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

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

解题思路

首先复制label和next指针，然后复制random指针，最后拆分新旧链表。

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
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head
        
        pre = head
        while pre:
            temp = pre.next
            pre.next = RandomListNode(pre.label)
            pre.next.next = temp
            pre = pre.next.next
            
        pre = head
        while pre:
            if pre.random:
                pre.next.random = pre.random.next
            pre = pre.next.next
        
        res = head.next
        cur = res
        pre = head
        while pre:
            pre.next = pre.next.next
            if cur.next:
                cur.next = cur.next.next
            pre = pre.next
            cur = cur.next
        
        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
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head
        
        pre = head
        while pre:
            temp = pre.next
            pre.next = Node(pre.val, None, None)
            pre.next.next = temp
            pre = pre.next.next
        
        pre = head
        while pre:
            if pre.random:
                pre.next.random = pre.random.next
            pre = pre.next.next
        
        res = head.next
        pre = res
        
        while head:
            head.next = head.next.next
            if pre.next:
                pre.next = pre.next.next
            head = head.next
            pre = pre.next
        
        return res

141. 环形链表

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：

你能用 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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        
        return False

142. 环形链表 II

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：
你是否可以不用额外空间解决此题？

解题思路

快慢指针，找到换之后，一个指针从头遍历。

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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

集合。将访问过的节点保存起来，遍历节点，如果节点在字典中，则说明重复是为环的入口；否则没有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        
        Dict = set()
        while head:
            if head in Dict:
                return head
            Dict.add(head)
            head = head.next
            
        return None

143. 重排链表

题目描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解题思路

  • 使用快慢指针先将链表从中间截断为两个链表，如果链表长度为奇数，则第一条链表长度多1；如1,2,3,4,5，拆分为1,2,3和4,5；
  • 将第二条链表翻转；即4,5翻转为5,4
  • 然后归并合并。
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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next or not head.next.next:
            return 
        
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        frontend = head
        backend = slow.next
        slow.next = None
        
        dummy = ListNode(0)
        dummy.next = backend
        cur = backend.next
        backend.next = None
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = temp
        backend = dummy.next
        
        p1 = frontend
        p2 = backend
        while p2:
            temp1 = p1.next
            temp2 = p2.next
            p1.next = p2
            p2.next = temp1
            p1 = temp1
            p2 = temp2

147. 对链表进行插入排序

题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

  • 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  • 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  • 重复直到所有输入数据插入完为止。

示例 1：

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

如果链表本来就是升序的，则往后遍历；
否则如果一个节点的值小于前一个节点，寻找合适的位置插入。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        cur = head
        while cur.next:
            if cur.val < cur.next.val:
                cur = cur.next
            else:
                pre = dummy
                while pre.next and pre.next.val < cur.next.val:
                    pre = pre.next
                temp = cur.next
                cur.next = temp.next
                temp.next = pre.next
                pre.next = temp
        
        return dummy.next

148. 排序链表

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

归并排序

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        mid = self.getmiddle(head)
        leftHead = head
        rightHead = mid.next
        mid.next = None
        
        left = self.sortList(leftHead)
        right = self.sortList(rightHead)
        
        return self.merge(left, right)
    
    def getmiddle(self, head):
        if not head or not head.next:
            return head
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow
    
    def merge(self, left, right):
        dummy = ListNode(0)
        pre = dummy
        while left and right:
            if left.val < right.val:
                pre.next = left
                left = left.next
            else:
                pre.next = right
                right = right.next
            pre = pre.next
        pre.next = left if left else right
        return dummy.next

160. 相交链表

题目描述

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

1
2
3
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

1
2
3
4
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        
        a, b = headA, headB
        while a or b:
            if not a:
                a = headB
            if not b:
                b = headA
            if a == b:
                return a
            a, b = a.next, b.next
 
        return None

第一次遍历，先计算两个链表的长度；
第二次遍历，让长的先走长度差，然后同时移动，判断是否有相同节点。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        
        countA = countB = 0
        a, b = headA, headB
        while a:
            a = a.next
            countA += 1
        while b:
            b = b.next
            countB += 1
            
        if countA > countB:
            for i in range(countA-countB):
                headA = headA.next
        else:
            for i in range(countB-countA):
                headB = headB.next
        
        while headA and headB:
            if headA == headB:
                return headA
            headA, headB = headA.next, headB.next
        
        return None

206. 反转链表

题目描述

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

迭代

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.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        cur = head.next
        head.next = None
        
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = temp
        
        return dummy.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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        return self.helper(head, ListNode(0))
    
    def helper(self, cur, dummy):
        if not cur:
            return dummy.next
        temp = cur.next
        cur.next = dummy.next
        dummy.next = cur
        cur = temp
        return self.helper(cur, dummy)

234. 回文链表

题目描述

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        
        left = head
        right = slow.next
        slow.next = None

        dummy = ListNode(0)
        dummy.next = right

        cur = right.next
        right.next = None
        
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = temp
        
        right = dummy.next

        
        while right:
            if right.val != left.val:
                return False
            right = right.next
            left = left.next
        
        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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        if not head or not head.next:
            return True
        
        left, right = self.splitLink(head)
        
        right = self.reverseLink(right)

        while right:
            if right.val != left.val:
                return False
            right = right.next
            left = left.next
            
        return True
    
    def splitLink(self, head):
        fast, slow = head, head
        while fast and fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        left = head
        right = slow.next
        slow.next = None
        
        return left, right
    
    def reverseLink(self, head):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        cur = head.next
        head.next = None
        
        while cur:
            temp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = temp
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bosol
        """
        if not head or not head.next:
            return True
        
        res = []
        while head:
            res.append(head.val)
            head = head.next
        
        return res == res[::-1]
Donate comment here
------------The End------------
0%