数据结构和算法 -- 链表

Posted on   |   In   |     |  

链表实现／移除节点／链表相加／链表部分翻转／链表改序/链表去重／链表划分／链表的环/链表公共节点问题/链表复制。

简介

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。数组 immutable length 和 no holes allowed 的特性带来的结果就是当 resize array 的时候需要 copy 原有的所有元素，当删除一个不在末尾的元素时，又要 shift 很多元素。而 Linked list 解决了这个问题，它的代价是需要额外的 4 bytes(32bit machine) 来储存指向下一个 node 的 reference，另外不允许随机访问元素。

线性表的两种存储方式

  • 顺序存储结构：随机读取，访问时是 O(1)
  • 链式存储结构：插入和删除 O(1)，访问时最坏是 O(n)

线性表的分类（根据指针域）

  • 单向链表(Singly linked list)
  • 双向链表(Doubly linked list)
  • 循环链表(Circular linked list)

这一篇主要讲的是链表（linked list）。链表是一种常见的线性数据结构。单向链表(singly linked list)，每个节点有一个 next 指针指向后一个节点，还有一个成员变量用以存储数值；双向链表(doubly Linked List)，多了一个 prev 指针指向前一个节点。与数组类似，搜索链表需要O(n)的时间复杂度，但是链表不能通过常数时间 O(1) 读取第 k 个数据。链表的优势在于能够以较高的效率在任意位置插入或删除一个节点。

Complexity

Linked list

addFirst: O(1)
insertBefore or insertAfter: O(n)
delete: O(n)
search: O(n)

Array

locate: O(1)
insert/delete: O(N)
search: not sorted -> linear search => O(N), sorted -> binary search => O(logN)
iteration: O(N)

基本策略

涉及头节点

当涉及对头节点的操作，考虑创建哑节点

修改单向链表的操作

考虑哪个节点的next指针会受到影响，则需要修正该指针；

反转链表

要把反转后的最后一个节点（即第一个节点）指向 null

删除某个节点

  • 由于需要知道前继节点的信息，而前继节点可能会导致表头产生变化，所以需要一些技巧 Dummy Node
  • 全部操作结束后，判断是否有环；若有，则置其中一端为 null

快慢指针

快速找出未知长度单链表的中间节点／涉及在链表中寻找特定位置

  • 设置两个指针 *fast 和 *slow 都指向头节点
  • *fast 移动速度是 *slow 的两倍
  • *fast 指向末尾节点时，*slow 正好就在中间

判断单链表是否有环

  • 设置两个指针 *fast 和 *slow 都指向头节点
  • *fast 移动速度是 *slow 的两倍
  • 如果 *fast == null 说明该单链表不是循环链表
  • 如果 *fast == *slow 说明该链表是循环链表

找倒数第 N 个节点

  • 设置两个指针 fast 和 slow 都指向头节点
  • *fast 先移动 N 步，然后两个指针一起前进
  • *fast 到达末尾时，*slow 即为倒数第 N 个节点

检验有效性

访问某个节点 cur.next 时，要检验 cur 是否为 null。（同理，访问 cur.next.next，检验 cur.next）

链表实现

Singly-linked list Implementation

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
# implement a singly-linked list
class Node(object):
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
    def addFirst(self, val):
        self.head = Node(val, self.head)
        return True
    def addLast(self, item):
        # if the list empty
        if not self.head:
            addFirst(val)
            return False
        # traverse to find the last element
        tmp = self.head
        while tmp.next:
            tmp = tmp.next
        # finally, add the new element into the list
        tmp.next = Node(item, None)
        return True
    def insertAfter(self, key, item):
        # find the location first with the given key
        tmp = self.head
        while tmp and tmp.val != key:
            tmp = tmp.next
        # as long as the key is in the list
        if tmp:
            toBeInserted = Node(item, tmp.next)
            tmp.next = toBeInserted
            return True  
        return False
    def insertBefore(self, key, item):
        # if the list is empty
        if not self.head:
            return False
        # if head has the key
        if self.head.val == key:
            addFirst(key)
            return True
        # key is not in the head
        prev = None
        cur = self.head
        while cur and cur.val != key:
            prev, cur = cur, cur.next
        # found it, then add new node into next of the previous
        if cur:
            prev.next = Node(item, cur)
            return True  
        return False
    def size(self):
        length = 0
        cur = self.head
        while cur:
            cur = cur.next
            length += 1
        return length
    def remove(self, key):
        if not self.head or not key:
            return False
        # if the key is found from the head element
        if self.head.val == key:
            head = head.next
            return True
        cur = self.head
        prev = None
        while cur and cur.val != key:
            prev = cur
            cur = cur.next
        # as long as key is found
        if cur:
            prev.next = cur.next
            return True
        return False
        '''
        while cur.next:
            if cur.next == data:
                cur.next = cur.next.next
                return True
            cur = cur.next
        return False
        #raise ValueError("Data not in list")
        '''
    def deleteList(self):
        self.head = None
        return True
    def search(self, data):
        cur = self.head
        while cur and cur.val != data:
            cur = cur.next
        return cur
    def printAll(self):
        cur = self.head
        while cur:
            print cur.val,
            cur = cur.next
        print

Leetcode 实例

移除节点(19.Remove Nth Node From End of List)

Problem

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

Solution

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
'''
A singly list is a particularly poor choice for a data structure when you frequently need to find the mth-to-last element!
Assumption:
- m is less than the length of linked list?
  if not, check first!
Solution:
You cannot traverse backward through a singly linked list, so may be we can store elements into another data structure so that we can look back, or for this problem, we can traverse from beginning of list.
Two-pass solution:
- first get the length of linked list, and then find the node before (length-n)th node, and node.next=node.next.next
- use dummy node
Follow-up:
one-pass solution:
- how to access nth node from the end?
    use two pointers, fast and slow, keep the distance n between fast and slow node
'''
# 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 not head.next:
            return None
        dummy=ListNode(0)
        dummy.next=head
        slow,fast=dummy,dummy
        for i in range(n):
            fast=fast.next
        while fast.next:
            fast,slow=fast.next,slow.next
        slow.next=slow.next.next
        return dummy.next
    '''
    # Two pass solution
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        length=0
        dummy=ListNode(0)
        dummy.next=head
        pointer1,pointer2=dummy,dummy
        while pointer1.next:
            length+=1
            pointer1=pointer1.next
        # find nth node
        for i in range(length-n):
            pointer2=pointer2.next
        pointer2.next=pointer2.next.next
        return dummy.next
        '''

链表相加(2.445. Add Two Numbers; 369. Plus One Linked List)

Problem(I)

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Similar problems (M) Multiply Strings (E) Add Binary (M) Add Two Numbers (M) Plus One Linked List
66.Plus One 67.Add Binary
43. Multiply Strings

Solution

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
'''
# Straight-forward
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # make sure a l1 is longer than l2
        p1, p2 = l1, l2
        while p1 and p2:
            p1 = p1.next
            p2 = p2.next
        if p1:
            p1, p2 = l1, l2
        else:
            p1, p2 = l2, l1
        # cal
        carry = 0
        res = ListNode(0)
        cur = res
        while p2:
            sum = p1.val + p2.val + carry
            carry = sum / 10
            sum %= 10
            cur.next = ListNode(sum)
            cur = cur.next
            p1, p2 = p1.next, p2.next
        while p1:
            sum = p1.val + carry
            carry = sum / 10
            sum %= 10
            cur.next = ListNode(sum)
            cur = cur.next
            p1 = p1.next
        if carry == 1:
            cur.next = ListNode(1)
        return res.next
        '''
# improved, doesn't need to know which list is longer
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
        output = head
        carry = 0
        while True:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            output.val = carry % 10
            carry = carry / 10
            if l1 or l2 or carry:
                output.next = ListNode(0)
                output = output.next
            else:
                break
        return head

注意考虑两个数位数不同的情况。
因为两位数相加进位最多影响后一位，不会影响 i+2 位，所以发现一个链表为空后，直接结束循环，最后只用进位和较长链表的当前节点相加，之后较长链表的 i+2 位直接照搬。
用这个结构可以实现大整数的计算。

Problem(II)

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Solution

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
# 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
        """
        p1, p2 = l1, l2
        s1, s2 = [], []
        while p1:
            s1.append(p1.val)
            p1 = p1.next
        while p2:
            s2.append(p2.val)
            p2 = p2.next
        '''
        # method 1: use a stack
        carry=0
        res=[]
        while True:
            if not s1 and not s2 and carry==0:
                break
            if s1:
                carry+=s1.pop()
            if s2:
                carry+=s2.pop()
            res.append(carry%10)
            carry/=10
        cur=ListNode(0)
        tmp=cur
        while res:
            tmp.next=ListNode(res.pop())
            tmp=tmp.next
        return cur.next
        '''
        # method 2: Linkedlist addFirst
        carry = 0
        cur = ListNode(None)
        while True:
            if not s1 and not s2 and carry == 0:
                break
            if s1:
                carry += s1.pop()
            if s2:
                carry += s2.pop()
            head = ListNode(carry % 10)
            head.next = cur if cur.val != None else None
            cur = head
            carry /= 10
        return cur

Problem(III)

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example:

1
2
3
4
5
Input:
1->2->3
Output:
1->2->4

Solution

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
'''
# use stack, O(n) space and O(n) time
class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        stack=[]
        res=ListNode(0)
        tmp=res
        while head:
            stack.append(head.val)
            head=head.next
        if stack[-1]<9:
            stack[-1]+=1
        else:
            i=len(stack)-1
            while i>=0 and stack[i]==9:
                stack[i]=0
                i-=1
            if i<0:
                tmp.next=ListNode(1)
                tmp=tmp.next
            else:
                stack[i]+=1
        for i in stack:
            tmp.next=ListNode(i)
            tmp=tmp.next
        return res.next
        '''
'''
# Do it recursively
class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def add(head):
            if not head:
                return 1
            carry = head.val + add(head.next)
            head.val = carry % 10
            return carry / 10
        carry = add(head)
        if carry == 1:
            tmp = ListNode(1)
            tmp.next = head
            head = tmp
        return head
        '''
# find the first node that is not 9: O(n) time and O(1) space
class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        notNine = None
        # find the first node that is not 9
        while cur:
            if cur.val != 9:
                notNine = cur
            cur = cur.next
        # plus 1
        if not notNine:
            notNine = ListNode(1)
            notNine.next = head
            head = notNine
        else:
            notNine.val += 1
        # update digits
        cur = notNine.next
        while cur:
            cur.val = 0
            cur = cur.next
        return head

链表的翻转(206.92.Reverse Linked List)

Problem(I)

Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

初步思考

每次走到最后一个数，把它放到最前面

1
2
3
4
5
6
1 -> 2 -> 3 -> 4 -> 5
=>
5 -> 1 -> 2 -> 3 -> 4
4 -> 5 -> 1 -> 2 -> 3
...
5 -> 4 -> 3 -> 2 -> 1

时间复杂度 $O(n^2)$

头插法

1
2
3
4
5
6
1 -> 2 -> 3 -> 4 -> 5
=>
2 -> 1 -> 3 -> 4 -> 5
3 -> 2 -> 1 -> 4 -> 5
...
5 -> 4 -> 3 -> 2 -> 1

时间复杂度 $O(n)$，空间复杂度 $O(1)$

要注意的是，把翻转后的最后一个节点（即原来的第一个节点）指向 Null(None)。
访问某个节点 cur.next，要检验 cur 是否为 None.

1
2
3
4
5
6
7
1 -> 2 -> 3 -> 4 -> 5
=>
1 -> None -> 2 -> 3 -> 4 -> 5
2 -> 1 -> None -> 3 -> 4 -> 5
3 -> 2 -> 1 -> None -> 4 -> 5
...
5 -> 4 -> 3 -> 2 -> 1 -> None

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = None
        while head:
            curr = head
            head = head.next
            curr.next= dummy
            dummy = curr
        return dummy

更简单。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = None
        while head:
            head.next,dummy,head=dummy,head,head.next # head.next=dummy 必须在 head=head.next之前
        return dummy

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return self._reverse(head)
    def _reverse(self, node, prev=None):
        if not node:
            return prev
        n = node.next
        node.next = prev
        return self._reverse(n, node)

Problem(II)

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

oup, 最后要返回的是 oup.next 指针
dummy 指针，在原来的 m-1 位置
cur 指针，在原来的 n 位置
reverse，在原来的 m 位置

dummy 指针，空转 m-1 次，找到第 m-1 个节点，即开始翻转的第一个结点的前一个；
利用 cur, reverse 按完全翻转的方法翻转[m,n]部分
最后修改两个指针，dummy.next 指向 reverse，dummy.next.next 指向第 n+1 个节点。

Solution

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
class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if m==n:
            return head
        # [1,m-1] nodes
        oup = ListNode(0)
        oup.next = head
        dummy = oup
        for i in range(m-1):
            dummy = dummy.next
        # reverse [m,n] nodes
        reverse = None
        cur = dummy.next
        for i in range(m,n+1):
            cur.next,reverse,cur = reverse,cur,cur.next
        # [n,end] nodes
        dummy.next.next = cur
        dummy.next = reverse
        return oup.next

链表改序（143. Reorder List）

Problem

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution

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
'''
Solution:
- Two-pass
    store all nodes in a stack, create a dummy node, every time while i < len(linked list), linked one node from linked list and one node from stack, and finally deal with odd or even number of length
Followup:
- One-pass and O(1)
    - find middle: use fast,slow pointers
    - reverse second half list: 1->2->3->4->null => null<-1<-2<-3<-4, for each node, point the next node of current to previous one, update the previous and next node, do the same thing
    - merge two lists
'''
# 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):
        if not head:
            return None
        # find middle
        fast,slow=head,head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
        # reverse list
        pre=None
        cur=slow
        while cur:
            # one line solution
            pre, cur.next, cur = node, pre, cur.next
            next=cur.next
            cur.next=pre
            pre=cur
            cur=next
        # merge list
        first,second=head,pre
        while second.next:
            first.next,first=second,first.next
            second.next,second=first,second.next
        return
    '''
    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: return
        stack=[]
        dummy=ListNode(0)
        dummy.next=head
        while dummy.next:
            stack.append(dummy.next)
            dummy=dummy.next
        dummy=ListNode(0)
        dummy.next=head
        length=len(stack)
        half_len=len(stack)/2
        for i in range(half_len):
            node,dummy=dummy.next.next,dummy.next
            # dummy.next,dummy=stack.pop(),dummy.next
            # this is wrong. suppose a=0,a,b=3,a => a=3,b=0
            dummy.next=stack.pop()
            dummy,dummy.next=dummy.next,node
        if length%2==1:
            dummy.next.next=None
        else:
            dummy.next=None
            '''

排序链表去重(82.83. Remove Duplicates from Sorted List I&II)

Problem(I)

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = head
        while head and head.next:
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
        return dummy

注意用到 head.next 一定要判断前一个节点 head 是否为空，同理，head.next.next 判断 head.next 是否为空。

Problem(II)

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        cur = dummy
        while head:
            while head.next and head.val == head.next.val:
                head = head.next
                if not head.next or head.val != head.next.val:
                    break
            else:
                cur.next = head
                cur = head
            head = head.next
        cur.next = None
        return dummy.next

考虑的 bad case: [1,1],[1,1,1]，所以最后的 cur.next = None 不能少，否则还会返回 [1]

链表的合并(21. Merge Two Sorted Lists)

快速排序对链表结构适用，然而不是所有排序都适合使用链表存储，如堆排序，不断寻找数组的 n/2 和 n 位置，用链表不大方便。

Problem

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution

Recursive
时间复杂度 O(N),空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l2 is None:
            return l1
        if l1 is None:
            return l2
        if l1.val < l2.val:
            head = l1
            head.next = self.mergeTwoLists(l1.next,l2)
        else:
            head = l2
            head.next = self.mergeTwoLists(l1,l2.next)
        return head

链表的划分（89.Partition List）

Problem

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution

用两个指针 left,right，小于 x 的用 left，大于 x 的用 right，最后连接 left,right

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
'''
Solution:
- create two lists less and greater, for each node in linkedlist, if it is less than x, add to less, else, add to greater, finally merge two lists. Time complexity: O(n), space complexity: O(1)
'''
class Solution(object):
    def partition(self,head,x):
        if not head:
            return None
        less,greater=ListNode(0),ListNode(0)
        less_cur,greater_cur=less,greater
        while head:
            if head.val<x:
                less_cur.next=head
                less_cur=less_cur.next
            else:
                greater_cur.next=head
                greater_cur=greater_cur.next
            head=head.next
        less_cur.next=greater.next
        greater_cur.next=None
        return less.next

这里要注意的是最后 right 要指向空，不然考虑 case [2,1]，会陷入[1,2,1,2…]的死循环中，因为 right_cur.next 指向了 head，形成了环。

链表的环 (141.142.Linked List Cycle I & II)

Problem(I)

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Solution

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
'''
Solution:
- For every node in linkedlist, check if it is in hashset, if not, add it, else, return True. Time complexity: O(n)
Followup:
- no extra space
    slow and fast pointers
'''
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            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
    '''
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        nodelist=set()
        while head.next:
            if head in nodelist:
                return True
            nodelist.add(head)
            head=head.next
        return False
    '''

Problem(II)

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Solution

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
'''
Solution:
- check if there's cycle
- Let's say, the cycle starts at node u, and the length of the cycle is L, Moreover, after x steps, fast catches slow, and the length between current node and u is p.
    then we can get for slow pointer, x=u+aL+p,
    for fast pointer, 2x=u+bL+p,
    => 2x-x=(b-a)L => x=nL.
    Now, think about that, at step x, if we travels u more steps, where are we?
    => u+x=u+nL.
    => We are at the start of the cycle, because we have covered the first u nodes once and the entire cycle n times.
Followup:
- find the length of cycle
    let slow move foward till meet with fast again
'''
# 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: return None
        fast,slow=head,head
        while True:
            if not fast or not fast.next:return None
            fast=fast.next.next
            slow=slow.next
            if fast==slow: break
        while head != fast:
            head,fast=head.next,fast.next
        return head

单链公共节点问题

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.


假设两个链表长度为 m，n，认为 m > n，两链表的第一个公共节点到尾节点一定是重合的。于是，可以分别遍历两个链表得到链表长度 m,n, 长链表空转 m-n 次，然后两链表齐头并进，同步遍历，直到找到公共节点。时间复杂度为 $O(m+n)$

如果链表存在环，则需要用快慢指针的方式计算公共节点。两个指针，每次分别移动 1 个／2 个节点。

Solution

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 getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        curA,curB = headA,headB
        lenA,lenB=0,0
        while curA:
            lenA += 1
            curA = curA.next
        while curB:
            lenB += 1
            curB = curB.next
        curA,curB = headA,headB
        if lenA > lenB:
            for i in range(lenA-lenB):
                curA = curA.next
        else:
            for i in range(lenB-lenA):
                curB = curB.next
        while curA != curB:
            curA = curA.next
            curB = curB.next
        return curA

一个从代码层面来讲的简洁版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None
        pa = headA # 2 pointers
        pb = headB
        while pa is not pb:
            # if either pointer hits the end, switch head and continue the second traversal,
            # if not hit the end, just move on to next
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next
        return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None
# the idea is if you switch head, the possible difference between length would be countered.
# On the second traversal, they either hit or miss.
# if they meet, pa or pb would be the node we are looking for,
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None

链表复制(138. Copy List with Random Pointer)

Problem

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution

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
'''
Solution:
- two-pass: consider normal copy of linkedlist, do similar stuff. first copy nodes and next pointer, then copy random pointer
            how to find new nodes in second pass? find with O(1) time => hashmap
- one-pass: first copy all nodes and store them into hashmap, then connect all nodes. time complexity: O(n), space complexity: O(n)
Followup:
- without hashmap?
'''
# 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):
    # copy nodes and next pointer
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head: return None
        cur=head
        hashmap={}
        while cur:
            # create nodes
            if cur not in hashmap:
                curCopy=RandomListNode(cur.label)
                hashmap[cur]=curCopy
            if cur.next and cur.next not in hashmap:
                nextCopy=RandomListNode(cur.next.label)
                hashmap[cur.next]=nextCopy
            if cur.random and cur.random not in hashmap:
                randomCopy=RandomListNode(cur.random.label)
                hashmap[cur.random]=randomCopy
            # connect nodes
            if cur.next: hashmap[cur].next=hashmap[cur.next]
            if cur.random: hashmap[cur].random=hashmap[cur.random]
            # next round
            cur=cur.next
        return hashmap[head]

参考链接：
编程起跑线 第 5 课 链表
Implementing a Singly Linked List in Python

徐阿衡 wechat
欢迎关注：徐阿衡的微信公众号
客官，打个赏呗~