一,单链表的创建
单链表的创建一般分为分为头插发和尾插法
- 头插法是每次将新的节点插入到头部,这样得到的链表顺序是逆序
- 尾插法是每次将新的节点插入到尾部,这样得到的链表顺序是正序的. ** 值得注意的是,采用尾插法的时候需要一个尾指针,时时刻刻指向链表的尾部 **
二,链表的操作
链表的插入无非是插入,删除操作.
- ** 在插入的删除的时候,一定要拿到他的前驱节点 **
- ** 为了便于链表的操作(例如,插入删除),一般使用带头结点的链表**
常见的插入删除题目如下:
两个链表相加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就指向了中点
相关题目
四,链表环的问题
- 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指向的节点时,走过的长度就是环的周长
