linked list
2019-07-19 本文已影响0人
cookyo
19 Remove Nth Node From End of List
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
newnode = ListNode(0)
newnode.next = head
fast = newnode
slow = newnode
for i in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return newnode.next
21 Merge Two Sorted Lists
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
tmpnode = ListNode(0)
p = tmpnode
while l1 and l2:
if l1.val <= l2.val:
tmpnode.next = l1
l1 = l1.next
tmpnode = tmpnode.next
else:
tmpnode.next = l2
l2 = l2.next
tmpnode = tmpnode.next
if l1:
tmpnode.next = l1
if l2:
tmpnode.next = l2
return p.next
23 Merge k Sorted Lists
from heapq import *
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
ans = None
p = None
for i in range(len(lists)):
if lists[i]:
heap.append((lists[i].val, i))
heapify(heap)
while heap:
(val, idx) = heappop(heap)
if not p:
p = ListNode(val)
ans = p
else:
p.next = ListNode(val)
p = p.next
lists[idx] = lists[idx].next
if lists[idx]:
heappush(heap, (lists[idx].val, idx))
return ans
24 Swap Nodes in Pairs
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
realhead = ListNode(0)
realhead.next = head
cur = realhead
while(cur.next and cur.next.next):
first = cur.next
second = cur.next.next
first.next = second.next
cur.next = second
second.next = first
cur = first
return realhead.next
25 Reverse Nodes in k-Group
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head or k == 1:
return head
realnode = ListNode(0)
realnode.next = head
pre = realnode
cur = head
i = 1
while cur:
if i % k == 0:
pre = self.reverse(pre, cur.next)
cur = pre.next
else:
cur = cur.next
i += 1
return realnode.next
def reverse(self, pre, nxt):
last = pre.next
cur = last.next
while cur != nxt:
last.next = cur.next
cur.next = pre.next
pre.next = cur
cur = last.next
return last
88 Merge Sorted Array
'''
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
'''
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
cur = m + n - 1
a = m - 1
b = n - 1
while a >= 0 and b >= 0:
if nums1[a] >= nums2[b]:
nums1[cur] = nums1[a]
a -= 1
cur -= 1
else:
nums1[cur] = nums2[b]
b -= 1
cur -= 1
while b >= 0:
nums1[cur] = nums2[b]
cur -= 1
b -= 1
148 Sort List
'''
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
'''
# 类似归并排序
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
pre = None
slow, fast = head, head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return self.merge(self.sortList(head), self.sortList(slow))
def merge(self, h1, h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next = h1
tail = h1
h1 = h1.next
else:
tail.next = h2
tail = h2
h2 = h2.next
tail.next = h1 or h2
return dummy.next