反转链表

  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 reverseList(self, head: ListNode) -> ListNode:
  8.         cur = head
  9.         if cur:
  10.             node = head.next
  11.             cur.next = None
  12.             while node:
  13.                 next_node = node.next
  15.                 # 插入到头部
  16.                 node.next = cur
  17.                 cur = node
  19.                 node = next_node
  21.         return cur

链表技巧

  • 1、合并两个有序链表 「虚拟头节点」技巧
  • 2、合并k个有序链表 优先级队列（二叉堆）
  • 3、寻找单链表的倒数第k个节点 双指针「虚拟头节点」技巧
  • 4、寻找单链表的中点 「快慢指针」的技巧
  • 5、判断单链表是否包含环并找出环起点
    • 每当慢指针slow前进一步，快指针fast就前进两步。
    • 如果fast最终遇到空指针，说明链表中没有环；
    • 如果fast最终和slow相遇，那肯定是fast超过了slow一圈，说明链表中含有环
  • 6、判断两个单链表是否相交并找出交点
    • 如果用两个指针p1和p2分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点c1。
    • 所以，解决这个问题的关键是，通过某些方式，让p1和p2能够同时到达相交节点c1。
    • 所以，我们可以让p1遍历完链表A之后开始遍历链表B，让p2遍历完链表B之后开始遍历链表A，这样相当于「逻辑上」两条链表接在了一起。
    • 如果这样进行拼接，就可以让p1和p2同时进入公共部分，也就是同时到达相交节点c1：

image.png
image.png