LeetCode单链表(LinkList)总结

一,单链表的创建

单链表的创建一般分为分为头插发和尾插法

• 头插法是每次将新的节点插入到头部,这样得到的链表顺序是逆序
• 尾插法是每次将新的节点插入到尾部,这样得到的链表顺序是正序的. ** 值得注意的是,采用尾插法的时候需要一个尾指针,时时刻刻指向链表的尾部 **

二,链表的操作

链表的插入无非是插入,删除操作.

• ** 在插入的删除的时候,一定要拿到他的前驱节点 **
• ** 为了便于链表的操作(例如,插入删除),一般使用带头结点的链表**

常见的插入删除题目如下:
两个链表相加LeetCode 2. Add Two Numbers
合并两个有序的链表LeetCode 21. Merge Two Sorted Lists
成对交换链表节点LeetCode 24. Swap Nodes in Pairs
每k个节点翻转LeetCode 25. Reverse Nodes in k-Group
链表逆转LeetCode 61. Rotate List
删除重复元素LeetCode 82. Remove Duplicates from Sorted List II

链表分块LeetCode 86. Partition List
删除链表节点LeetCode 203. Remove Linked List Elements

三,链表的中点

求链表中点的方法
使用两个指针fast,low, fast和low同时向前跳, fast每次向前跳两个节点, low每次向前跳一个节点,当fast调到尾部的时候,low就指向了中点
相关题目

• 19. Remove Nth Node From End of List
• 234. Palindrome Linked List

四,链表环的问题

• 1,链表是否存在环?

• 2,链表环的入口节点?
• 3,链表中存在环,环的长度?

• 1,对于问题1
  我们可以使用两个指针fast,low, fast每次前进两步,low每次前进一次,如果fast和low都到链表尾部且为空,则不在环如果fast和low第一次相遇到某一节点,且不为空,则存在环.

• 2,对于问题2
  若存在环,第一次相遇后, 将fast指向头结点,然后fast和low都每次向前移动一步,那么再次相交的节点就是环的入口节点

• 3,对于问题3
  假设头结点到环的入口节点为A, 环的入口节点到fast和low第一次相遇的节点距离为B, 环的长度为C.
  我们可以得出如下推论:
  1)第一次相遇时,low走过的长度是 A+B, fast走过的长度是2(A+B)
  2)fast比low走的距离刚好多环一周C.
  所以 2(A+B) - (A+B) = C ====> A+B = C

由上可知,当fast和low第一次相遇后, 将fast指向头节点,然后fast每次前进一步,而low不动,当其到达low指向的节点时,走过的长度就是环的周长

链表环.jpg

• 相关题目
  LeetCode 141. Linked List Cycle
  LeetCode 142. Linked List Cycle II