链表 - 《LeetCode Notebook》

206. Reverse Linked List

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        cur = self.reverseList(head.next)  # 一路走到尾节点
        head.next.next = head
        head.next = None                   # 避免成环
        return cur                         # 永远返回新的头节点

时间复杂度：

空间复杂度：链表 - 图2 ，取决于递归调用的栈空间

class Solution:
  def reverseList(self, head: ListNode) -> ListNode:
      l, m = None, head
      while m:
          r = m.next
          m.next = l
          l, m = m, r
      return l

时间复杂度：
空间复杂度：

92. Reverse Linked List II

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode(-1, head)
        l, m = dummy, head
        for _ in range(left - 1):
            l, m = l.next, m.next
        for _ in range(right - left):
            r = m.next
            l.next, m.next, r.next = r, r.next, l.next
        return dummy.next

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode(-1, head)
        pre = nxt = l = r = dummy
        for _ in range(left - 1):
            pre = pre.next
        l = pre.next
        for _ in range(right):
            r = r.next
        nxt = r.next
        def reverse(head, tail):    # 反转部分链表并返回'头and尾'
            tail.next = None        # 以m为基准遍历，避免走出[head, tail]
            l, m = None, head
            while m:
                r = m.next
                m.next = l
                l, m = m, r
            return tail, head
        l, r = reverse(l, r)
        pre.next, r.next = l, nxt
        return dummy.next

时间复杂度：
空间复杂度：

25. Reverse Nodes in k-Group

class Solution:
    def reverse(self, head, tail):                    # 翻转[head, tail]并返回'头and尾'
        tail.next = None
        l, m = None, head
        while m:
            r = m.next
            m.next = l
            l, m = m, r
        return tail, head
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        tail = head
        for _ in range(k - 1):
            tail = tail.next
            if not tail:                              # 不足k个元素，不执行翻转直接返回
                return head    
        next_head = tail.next
        next_head = self.reverseKGroup(next_head, k)  # 将后方链表翻转
        head, tail = self.reverse(head, tail)
        tail.next = next_head
        return head

时间复杂度：

空间复杂度：链表 - 图8

class Solution:
  def reverse(self, head, tail):                    # 翻转[head, tail]并返回'头and尾'
      tail.next = None
      l, m = None, head
      while m:
          r = m.next
          m.next = l
          l, m = m, r
      return tail, head
  def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
      dummy = ListNode(-1, head)
      pre = tail = dummy
      while head:
          for _ in range(k):
              tail = tail.next
              if not tail:                          # 长度不足k，不执行翻转
                  return dummy.next
          next_head = tail.next
          head, tail = self.reverse(head, tail)
          pre.next, tail.next = head, next_head
          pre, head = tail, next_head
      return dummy.next

时间复杂度：
空间复杂度：

21. Merge Two Sorted Lists

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        elif not list2:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

时间复杂度：
空间复杂度：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        p = dummy 
        while list1 and list2:
            if list1.val < list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        p.next = list1 if list1 else list2
        return dummy.next

时间复杂度：
空间复杂度：

23. Merge k Sorted Lists

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        min_heap = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(min_heap, (lists[i].val, i))
                lists[i] = lists[i].next

        dummy = ListNode(-1)
        p = dummy

        while min_heap:
            val, i = heapq.heappop(min_heap)
            p.next = ListNode(val)
            p = p.next

            if lists[i]:
                heapq.heappush(min_heap, (lists[i].val, i))
                lists[i] = lists[i].next

        return dummy.next

时间复杂度：
空间复杂度：，小根堆中的元素不超过个（排序链表的数目）

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

        def merge(lists, low, high):
            if low >= high:
                return lists[low]

            mid = low + high >> 1
            l1 = merge(lists, low, mid)
            l2 = merge(lists, mid+1, high)
            return merge_two_lists(l1, l2)

        def merge_two_lists(list1, list2):
            if not list1:
                return list2
            elif not list2:
                return list1
            elif list1.val < list2.val:
                list1.next = merge_two_lists(list1.next, list2)
                return list1
            else:
                list2.next = merge_two_lists(list1, list2.next)
                return list2

        if not lists:
            return
        return merge(lists, 0, len(lists) - 1)

时间复杂度：，是每个链表的最长长度
空间复杂度：

143. Reorder List `大杂烩`

找到原链表中点
将后半段翻转，返回翻转后的头节点

合并（依次取一个链表的节点）两段链表

class Solution:
 def reorderList(self, head: ListNode) -> None:
     def reverse_list(p):
         l, m = None, p
         while m:
             r = m.next
             m.next = l
             l, m = m, r
         return l

     def merge_2_lists(l1, l2):
         while l1 and l2:
             tmp1, tmp2 = l1.next, l2.next
             l1.next, l2.next = l2, tmp1
             l1, l2 = tmp1, tmp2

     dummy = ListNode(-1, head)
     slow = fast = dummy
     while fast and fast.next:       # slow停在前半段末尾
         slow = slow.next
         fast = fast.next.next

     p1, p2 = head, slow.next
     slow.next = None
     p2 = reverse_list(p2)           # 翻转后半部分

     merge_2_lists(p1, p2)

时间复杂度：
空间复杂度：

328. Odd Even Linked List

按奇偶分割链表 - 图23 合并

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        odd_head, even_head = head, head.next
        odd, even = odd_head, even_head

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next

        odd.next = even_head
        return odd_head

时间复杂度：
空间复杂度：

19. Remove Nth Node From End of List

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1, head)
        left, right = dummy, dummy.next

        for _ in range(n):
            right = right.next

        while right:
            left = left.next
            right = right.next

        left.next = left.next.next
        return dummy.next

时间复杂度：
空间复杂度：

234. Palindrome Linked List

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True

        slow = fast = head
        l, m = None, head

        # 1.找到链表中点，并反转前半部分
        while fast and fast.next:
            slow = slow.next         # 先移动快慢指针
            fast = fast.next.next

            m.next = l               # 再反转（前半部分）
            l, m = m, slow

        # 2.特判：链表长度为奇数
        if fast:
            m = m.next

        # 3.比较两部分链表
        while l and m:
            if l.val != m.val:
                return False
            l, m = l.next, m.next

        return True

时间复杂度：
空间复杂度：

剑指 Offer 35. 复杂链表的复制

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return

        dic = dict()                           # Node(old) -> Node(new)

        # 1.复制并将映射关系记录在哈希表
        p = head
        while p:
            dic[p] = Node(p.val)
            p = p.next

        # 2.构建copy节点的next和random指针
        p = head
        while p:
            dic[p].next = dic.get(p.next)      # 使用get()，避免空
            dic[p].random = dic.get(p.random)  # 使用get()，避免空
            p = p.next

        return dic[head]

时间复杂度：

空间复杂度：链表 - 图31

class Solution:
  def copyRandomList(self, head: 'Node') -> 'Node':
      if not head:
          return

      # 1.复制节点并拼接
      p = head
      while p:
          tmp = Node(p.val)
          p.next, tmp.next = tmp, p.next
          p = p.next.next

      # 2.构建random指针
      p = head
      while p:
          if p.random:    # 判空条件
              p.next.random = p.random.next
          p = p.next.next

      # 3.拆分
      copy_head = head.next
      p, q = head, head.next
      while q.next:       # 判空条件
          p.next = p.next.next
          q.next = q.next.next
          p, q = p.next, q.next

      # 4.处理原链表尾节点指针
      p.next = None
      return copy_head

时间复杂度：
空间复杂度：

2. Add Two Numbers

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        p = dummy
        carry = 0

        while l1 or l2:
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0

            bit_sum = num1 + num2 + carry
            bit = bit_sum % 10 
            carry = bit_sum // 10

            p.next = ListNode(bit)
            p = p.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        if carry:
            p.next = ListNode(carry)

        return dummy.next

时间复杂度：
空间复杂度：，不考虑返回值的空间占用

链表

143. Reorder List 大杂烩

143. Reorder List `大杂烩`