24. 两两交换链表中的节点

https://leetcode-cn.com/problems/swap-nodes-in-pairs/
链表操作时尽量使用dummy节点
注意post节点更新的时机

  1. class Solution:
  2.     def swapPairs(self, head: ListNode) -> ListNode:
  3.         if not head or not head.next:
  4.             return head
  5.         dummy = ListNode(-1)
  6.         dummy.next = head
  7.         pre = dummy
  8.         while head and head.next:
  9.             post = head.next
  10.             # swap
  11.             head.next = post.next
  12.             post.next = head
  13.             pre.next = post
  14.             # update pointer
  15.             pre = head
  16.             head = head.next
  17.         return dummy.next

206. 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/
迭代

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         cur = None
  4.         while head:
  5.             tmp = head.next
  6.             head.next = cur
  7.             cur = head
  8.             head = tmp
  9.         return cur

递归
image.png

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         if not head or not head.next:
  4.             return head
  6.         newHead = self.reverseList(head.next)
  7.         head.next.next = head
  8.         head.next = None
  9.         return newHead

92. 反转链表 II

https://leetcode-cn.com/problems/reverse-linked-list-ii/
第一个版本写的比较丑，一个指针指向m的pre，一个指针指向n，一直把pre_m.next移动到n的后面就可以了
这种情况需要特殊考虑当m是1的时候，也就是要从第头指针开始反转的情况
第二种： 其实没有必要找到n点，只需要每次把m.next挪到m之前, pre_m之后即可

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
  8.         if m == n:
  9.             return head
  10.         dummy = ListNode(-1)
  11.         dummy.next = head
  12.         pre = dummy
  13.         i = 0
  14.         while i < m-1:
  15.             pre = pre.next
  16.             i += 1
  17.         pre_m = pre
  18.         while i < n:
  19.             pre = pre.next
  20.             i += 1
  21.         node_n = pre
  22.         i = 0
  23.         while i < n - m :
  24.             # 从前面拿出来
  25.             node = pre_m.next
  26.             pre_m.next = pre_m.next.next
  27.             # 放到后面去
  28.             tmp = node_n.next
  29.             node_n.next = node
  30.             node.next = tmp
  31.             i += 1
  32.         return dummy.next

只需要找到反转的起始位置, 使用头插法
用一个守卫节点指向反转起始位置,设为g
起始位置为p, 每次将p.next放到g.next. 循环m-n次

  1. class Solution:
  2.     def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
  3.         if left == right:
  4.             return head
  5.         dummy = ListNode(-1)
  6.         dummy.next = head
  7.         pre = dummy
  8.         i = 0
  9.         while i < left-1:
  10.             pre = pre.next
  11.             i += 1
  12.         g = pre
  13.         p = g.next
  14.         for i in range(right-left):
  15.             tmp = p.next
  16.             p.next = tmp.next
  17.             tmp.next = g.next
  18.             g.next = tmp
  19.         return dummy.next

445. 两数相加 II

https://leetcode-cn.com/problems/add-two-numbers-ii/

  1. class Solution:
  2.     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         stack_l1 = []
  4.         stack_l2 = []
  5.         while l1:
  6.             stack_l1.append(l1.val)
  7.             l1 = l1.next
  8.         while l2:
  9.             stack_l2.append(l2.val)
  10.             l2 = l2.next
  11.         carry = 0
  12.         while stack_l2 or stack_l1 or carry:
  13.             a = stack_l2.pop() if stack_l2 else 0
  14.             b = stack_l1.pop() if stack_l1 else 0
  15.             summary = a+b+carry
  16.             node = ListNode(summary%10)
  17.             carry = summary//10
  18.             node.next = head
  19.             head = node
  20.         return head

21. 合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/
迭代

  1. class Solution:
  2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         dummy = ListNode(-1)
  4.         res = dummy
  5.         while l1 and l2:
  6.             if l2.val<l1.val:
  7.                 res.next = l2
  8.                 l2 = l2.next
  9.             else:
  10.                 res.next = l1
  11.                 l1 = l1.next
  12.             res = res.next
  13.         res.next = l1 if l1 else l2
  14.         return dummy.next

递归

  1. class Solution:
  2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         if not l1:return l2
  4.         if not l2:return l1
  6.         if l1.val<l2.val:
  7.             l1.next = self.mergeTwoLists(l1.next, l2)
  8.             return l1
  9.         else:
  10.             l2.next = self.mergeTwoLists(l1, l2.next)
  11.             return l2

23. 合并K个升序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/
21的升级版

  1. 循环遍历k个链表， python会TLE

    1. class Solution:
    2.  def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    3.      if not lists:
    4.          return
    5.      dummy = ListNode(0)
    6.      res = dummy
    7.      size = len(lists)
    8.      while True:
    9.          minNode = None
    10.          minPointer = -1
    11.          for i in range(len(lists)):
    12.              if not lists[i]:
    13.                  continue
    14.              if not minNode or lists[i].val < minNode.val:
    15.                  minNode = lists[i]
    16.                  minPointer = i
    17.          if minPointer==-1:
    18.              break
    19.          res.next = minNode
    20.          res = res.next
    21.          lists[minPointer] = lists[minPointer].next
    22.      return dummy.next

    分治， 归并排序应用于链表

    1. class Solution:
    2.  def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    3.      if not lists:
    4.          return
    5.      def mergeTwoLists(l1,l2):
    6.          dummy = ListNode(-1)
    7.          res = dummy
    8.          while l1 and l2:
    9.              if l2.val<l1.val:
    10.                  res.next = l2
    11.                  l2 = l2.next
    12.              else:
    13.                  res.next = l1
    14.                  l1 = l1.next
    15.              res = res.next
    16.          res.next = l1 if l1 else l2
    17.          return dummy.next
    19.      def merge(lists, lo, hi):
    20.          if lo==hi:
    21.              return lists[lo]
    23.          mid = lo + (hi-lo)//2
    24.          l1 = merge(lists, lo, mid)
    25.          l2 = merge(lists, mid+1, hi)
    26.          return mergeTwoLists(l1,l2)
    28.      return merge(lists, 0 , len(lists)-1)

    拍案叫绝，给ListNode class增加lt方法， 就可以用来比较大小

    1. class Solution:
    2.  def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    4.      def __lt__(self, other):
    5.          return self.val < other.val
    6.      ListNode.__lt__ = __lt__
    8.      import heapq
    9.      heap = []
    10.      dummy = ListNode(-1)
    11.      p = dummy
    13.      for l in lists:
    14.          if l:
    15.              heapq.heappush(heap, l)
    16.      while heap:
    17.          node = heapq.heappop(heap)
    18.          p.next = ListNode(node.val)
    19.          p = p.next
    20.          if node.next:
    21.              heapq.heappush(heap, node.next)
    23.      return dummy.next

    25. K 个一组翻转链表

    https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
    一旦看到翻转顺序， 请第一时间先想到stack！

    160. 相交链表

    https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
    我一开始想到的是用哈希表，两个链表都往哈希表里存，如果一个链表存的时候发现已经存在了，那么肯定是另外一个链表存进去的，此时返回这个节点
    但是这样空间复杂度太高， 这道题可以用空间复杂度为0(1)的解法， 也就是长短链表拼接，假设两个链表相交，那么相交的部分长度是相等的，我们分为一个长链表一个短链表， 两个链表从表头开始循环，如果长的走完了，那么就走短的，如果短的走完了，那么就走长的； 如果有交点，那么他们会同时抵达交点，此刻走过的路程都是等于 长+短+相交， 顺序是 长+相交+短 和 短+相交+长。
    这里最巧妙的地方在于边界条件的处理，要把最后一个节点之后的None也加到循环中来， 这样如果两个链表不相交，那么最终会在等于None的地方相交（满足退出条件）

    1. class Solution:
    2.  def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    3.      ha, hb = headA, headB
    4.      while ha!=hb:
    5.          ha = ha.next if ha else headB
    6.          hb = hb.next if hb else headA
    7.      return ha

    138. 复制带随机指针的链表

    https://leetcode-cn.com/problems/copy-list-with-random-pointer/ ```python “””

    Definition for a Node.

    class Node: def init(self, x: int, next: ‘Node’ = None, random: ‘Node’ = None):

    1.  self.val = int(x)
    2.  self.next = next
    3.  self.random = random

    “””

class Solution: def copyRandomList(self, head: ‘Node’) -> ‘Node’: lookup = {} if not head: return None p = head while p: lookup[p] = Node(p.val) p = p.next p = head while p: lookup[p].next = lookup[p.next] if p.next else None p = p.next p = head while p: lookup[p].random = lookup[p.random] if p.random else None p = p.next return lookup[head]

  1. <a name="1lT4Q"></a>
  2. #### [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
  3. [https://leetcode-cn.com/problems/palindrome-linked-list/](https://leetcode-cn.com/problems/palindrome-linked-list/)<br />简单的题不简单的做,  涉及快慢指针, 链表反转<br />用快慢指针找到链表的中间位置 ( 注意链表长度的奇偶分别判断)<br />反转链表后半部分<br />此时两个指针分别指向链表的开头 和 链表中间(后半部分已经翻转)<br />逐个对比, 判断回文
  4. ```python
  5. # Definition for singly-linked list.
  6. # class ListNode:
  7. #     def __init__(self, val=0, next=None):
  8. #         self.val = val
  9. #         self.next = next
  10. class Solution:
  11.     def isPalindrome(self, head: ListNode) -> bool:
  12.         if not head or not head.next:
  13.             return True
  14.         fast,slow = head,head
  15.         # fast pointer is twice faster than slow pointer
  16.         while fast and fast.next:
  17.             slow = slow.next
  18.             fast = fast.next.next
  19.         # if fast pointer is not None, it means the length of linkedlist is odd
  20.         if fast:
  21.             slow = slow.next
  22.         # reverse the linkedlist leading by slow pointer
  23.         pre = ListNode(-1)
  24.         pre.next = slow
  25.         while slow.next:
  26.             post = slow.next
  27.             slow.next = post.next
  28.             post.next = pre.next
  29.             pre.next = post
  30.         slow = pre.next
  31.         # compare from head
  32.         while head and slow:
  33.             if head.val!=slow.val:
  34.                 return False
  35.             head = head.next
  36.             slow = slow.next
  37.         return True