linked list

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