Part 4 – 综合题
现在基础技术，Dummy Node和Two Pointers技术我们都介绍完毕，下面介绍几道综合题目来讲解下他们是如何在复杂题目中应用的。
143. Reorder List
https://leetcode.com/problems/reorder-list/description/
找链表中点 + 反转链表 + 增加结点。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
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
walker = runner = head
while runner.next and runner.next.next:
walker = walker.next
runner = runner.next.next
head2 = walker.next
walker.next = None
pre = None
cur = head2
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
walker = head
runner = pre
while walker and runner:
next = runner.next
runner.next = walker.next
walker.next = runner
runner = next
walker = walker.next.next
23. Merge k Sorted Lists
https://www.jianshu.com/p/cb1a04e7d921
138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/description/
第一种解法，使用defaultdict巧妙的根据原链表的指针关系构建新的链表。时间复杂度为O(n)，空间复杂度为O(n)。
代码如下：
# 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
"""
res_dict = collections.defaultdict(lambda: RandomListNode(0))
res_dict[None] = None
cur = head
while cur:
res_dict[cur].label = cur.label
res_dict[cur].next = res_dict[cur.next]
res_dict[cur].random = res_dict[cur.random]
cur = cur.next
return res_dict[head]
第二种做法，先在原链表中复制自己并构建指针结构，然后再拆解成原链表和目标链表两个链表即可。
代码如下：
# 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
"""
cur = head
while cur:
copy_node = RandomListNode(cur.label)
copy_node.next = cur.next
cur.next = copy_node
cur = cur.next.next
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
cur = head
pre = dummy = RandomListNode(0)
while cur:
pre.next = cur.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
return dummy.next
147. Insertion Sort List
https://leetcode.com/problems/insertion-sort-list/description/
使用了Dummy Node技术，原理和Insertion Sort一模一样。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
pre = dummy = ListNode(0)
while head:
pre = dummy
while pre.next and pre.next.val < head.val:
pre = pre.next
nxt = head.next
head.next = pre.next
pre.next = head
head = nxt
return dummy.next
