DarkAlexWang's Blog
0%

LinkedList系列

Posted on Edited on In Views: Valine:
Symbols count in article: 3.7k Reading time ≈ 3 mins.

NOTE

搬运文章，原创作者:http://joshuablog.herokuapp.com/
Just for study purpose, I don’t hold the copyright, if this is affecting anyone, please let me know.

LinkedList系列总结

24/27
[x] Easy
[x] Medium
[x] Hard
这种题，多画图，一步步来，确定哪个node指向哪个node就会好一点,之后把图放上来，会更容易复习！

基础

dummyNode

适用于头节点需要进行操作，增删改，亦或者保存头节点，不被后续操作改变

1
2
3
dummy = ListNode(0)
dummy.next = head
curr = head

reverseList

Iterative版本，简要来说就是记录下一节点，当前节点指向上一节点，同步移动上一节点和当前节点。最后的curr为空，prev为头也就是最初链表的最后一个元素

1
2
3
4
5
6
7
8
prev = None
curr = head
while curr:
    nextNode = curr.next
    curr.next = prev
    prev = curr
    curr = nextNode
return prev

Recursive版本的，一直到底，然后倒叙指针

1
2
3
4
5
second = head.next
head.next = None
rest = self.reverseList(second)
second.next = head
return rest

变种1 92. Reverse Linked List II
除了移动节点之外，关键是链接头和尾

1
2
pre.next.next = curr //pre.next 为最初的头，.next则链接后来的尾和最初的尾 1-2-3-4-5，1-4-3-2-5，2-5
pre.next = newHead // 1-4

快慢指针

用于检测环和找中点,见于
141. Linked List Cycle
142. Linked List Cycle II
·234. Palindrome Linked List

1
2
3
4
fast, slow = head, head
while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

Medium版本

·369. Plus One Linked List
·445. Add Two Numbers II
本质上用stack保存节点信息，然后不断在前方添加节点

1
2
3
4
5
node.val = add_value % 10
carry = ListNode(add_value / 10)
carry.next = node
node = carry
add_value /= 10

Merge，Move系列
·21. Merge Two Sorted Lists
·328. Odd Even Linked List
·86. Partition List

1
2
3
4
5
6
7
8
9
curr = dummy
while l1 and l2:
    if l1.val < l2.val:
        curr.next = l1
        l1 = l1.next
    else:
        curr.next = l2
        l2 = l2.next
    curr = curr.next

保证两个list都存在，然后剩余的append在后面；然后移动节点的过程中要数好步伐while even and even.next:
·160. Intersection of Two Linked Lists
·19. Remove Nth Node From End of List

`61. Rotate List
trick的地方是找到最后一个node，并且链接第一个，使用常用模版，不过稍加改动，因为要找到最后一个node而不是长度，所以要提前终止循环

1
2
3
4
5
6
length = 1
while curr.next:
    curr = curr.next
    length += 1
curr.next = head
move = length-1-k%length

综合
`143. Reorder List
结合 以上多种方法，快慢指针找中点，反转，merge

1
2
3
4
5
mid = self.findMiddle(head)
tail = self.reverse(mid.next)
mid.next = None

self.merge(head, tail)

`23. Merge k Sorted Lists
一种方法是利用merge two list然后不断divide and conquer，另外一种比较简洁的是利用PriorityQueue，然后不断put和poll()进而每一个node都是所有优先队列中最小的一个

1
2
3
4
5
6
7
8
9
q = PriorityQueue()
for node in lists:
    if node: ## empty
        q.put((node.val, node))
while q.qsize():
    curr.next = q.get()[1]
    curr = curr.next
    if curr.next:
        q.put((curr.next.val, curr.next))

`82. Remove Duplicates from Sorted List II
因为要移除所有重复的node，所以势必要prev保存上一节点，然后如果中间因为重复节点而curr！= prev.next，要把prev节点的next放到curr的next节点，因为curr为重复节点的最后一个

1
2
3
4
5
6
7
8
9
while curr:
	while curr.next and curr.val == curr.next.val: ## [1]
		curr = curr.next
		if prev.next != curr:
			prev.next = curr.next
			curr = prev.next
		else:
			prev = prev.next
			curr = curr.next

`109. Convert Sorted List to Binary Search Tree
用helperfunction帮助，每一步找出子链表的中点，然后分别递归left和right节点。

1
2
3
4
5
6
while fast!= tail and fast.next != tail:
    fast = fast.next.next
    slow = slow.next
root = TreeNode(slow.val)
root.left = self.helper(head, slow)
root.right = self.helper(slow.next, tail)

·148. Sort List
分治法，然后分别对子链表merge

1
2
3
4
5
6
7
8
9
10
11
12
prev,fast, slow =  None, head, head
while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next

prev.next = None ## cut the middle

l1 = self.sortList(head)
l2 = self.sortList(slow)

return self.merge(l1, l2)

·24. Swap Nodes in Pairs
这道题勤画图，一步步来就好，iterative的方法比较烦，不过是Reverse Nodes in k-Group的简化版，那道题是LinkedList集大成者

1
2
3
4
5
6
7
8
while curr.next and curr.next.next:
    first = curr.next   # 1
    second = curr.next.next #2

    first.next = second.next # 1-3
    curr.next = second  #-2
    curr.next.next = first  #2-1
    curr = curr.next.next # 1

`25. Reverse Nodes in k-Group
这道题是一道典型的综合题，适合复习备考多刷。它的子function是reverseList的改良，因为需要保存头节点和尾节点，所以需要设置lastNode和nextNode，然后与之相对应的就是lastNode不断和后面的节点进行调换。可以看看对比

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
/*
 * 0->1->2->3->4->5->6
 * |           |
 * pre        next
 *
 * after calling pre = reverse(pre, next)
 *
 * 0->3->2->1->4->5->6
 *          |  |
 *          pre next
 */

def reverseNode(self, pre, nextNode):
    lastNode = pre.next
    curr = lastNode.next

    while curr != nextNode:
        lastNode.next = curr.next
        curr.next = pre.next
        pre.next = curr
        curr = lastNode.next
    return lastNode

def reverseList(self, head):
	if not head or not head.next:
	    return head
	prev = None
	curr = head
	while curr:
	    nextNode = curr.next
	    curr.next = prev
	    prev = curr
	    curr = nextNode
	return prev