Part 4 – 綜合題
現(xiàn)在基礎技術(shù)，Dummy Node和Two Pointers技術(shù)我們都介紹完畢摔桦，下面介紹幾道綜合題目來講解下他們是如何在復雜題目中應用的。
143. Reorder List
https://leetcode.com/problems/reorder-list/description/
找鏈表中點 + 反轉(zhuǎn)鏈表 + 增加結(jié)點。
代碼如下：
# 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
http://www.reibang.com/p/cb1a04e7d921
138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/description/
第一種解法杖小，使用defaultdict巧妙的根據(jù)原鏈表的指針關(guān)系構(gòu)建新的鏈表荒叶。時間復雜度為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]
第二種做法些楣，先在原鏈表中復制自己并構(gòu)建指針結(jié)構(gòu)脂凶，然后再拆解成原鏈表和目標鏈表兩個鏈表即可。
代碼如下：
# 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技術(shù)愁茁，原理和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
