找链表的中点：

  • 五个节点中间节点找 3 3+2
  • 四个节点中间节点找 2 2+2

需要 slow 从 head 出发，fast 从 head.next 出发。
while 循环的时候需要判断 fast and fast.next

  1. 21. 合并两个有序链表 - 找链表的中点
  2. slow,fast=head,head.next
  3. while fast and fast.next:
  4.     fast,slow=fast.next.next,slow.next
  5. slow.next,mid=None,slow.next

归并排序两个链表

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def sortList(self, head: ListNode) -> ListNode:
  9.         if not head or not head.next:return head
  10.         # Cut
  11.         slow,fast=head,head.next
  12.         while fast and fast.next:
  13.             fast,slow=fast.next.next,slow.next
  14.         slow.next,mid=None,slow.next
  15.         # Recursion
  16.         left,right=self.sortList(head),self.sortList(mid)
  17.         # Merge
  18.         h=res=ListNode(0)
  19.         while left and right:
  20.             if left.val<right.val:h.next,left=left,left.next
  21.             else:h.next,right=right,right.next
  22.             h=h.next
  23.         h.next=left if left else right
  24.         return res.next

链表逆序

  1. def reverse(self, head):
  2.     pre = None
  3.     curr = head
  4.     while curr:
  5.         nextNode = curr.next
  6.         curr.next = pre
  7.         pre = curr
  8.         curr = nextNode
  9.         return pre

双向链表

双向链表的定义

  1. struct doubleLinkedNode {
  2.     int key, value;
  3.     doubleLinkedNode* prev;
  4.     doubleLinkedNode* next;
  5.     doubleLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {};
  6.     doubleLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {};
  7. };

头节点后面添加 / 删除节点 / 尾节点前面删除 / 移动节点到头部

  1. void addToHead(doubleLinkedNode* node) {
  2.     node->prev = head;
  3.     node->next = head->next;
  4.     head->next->prev = node;
  5.     head->next = node;
  6. }
  7. void removeNode(doubleLinkedNode* node) {
  8.     node->prev->next = node->next;
  9.     node->next->prev = node->prev;
  10. }
  11. void moveToHead(doubleLinkedNode* node) {
  12.     removeNode(node);
  13.     addToHead(node);
  14. }
  15. doubleLinkedNode* removeTail() {
  16.     doubleLinkedNode* node = tail->prev;
  17.     removeNode(node);
  18.     return node;
  19. }