算法-链表
云想衣裳花想容，春风拂槛露华浓。
简介：算法-链表
一、从尾到头打印链表
1、题目描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。输入：
{1,2,3}
返回值：
[3,2,1]
2、解题思路
使用递归
要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。
1 import java.util.*;
2 public class Solution {
3 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
4 ArrayList<Integer> ret = new ArrayList<>();
5 if (listNode != null) {
6 // 递归
7 ret.addAll(printListFromTailToHead(listNode.next));
8 ret.add(listNode.val);
9 }
10 return ret;
11 }
12 }
View Code
二、删除链表中重复的节点
1、题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
输入：
{1,2,3,3,4,4,5}
返回值：
{1,2,5}
2、解题思路
借助辅助头结点，可避免单独讨论头结点的情况。设置两个结点 pre 和 cur，当 cur 和 cur.next 值相等，cur 一直向前走，直到不等退出循环，这时候 cur 指的值还是重复值，调整 cur 和 pre 的指针再次判断。
1 /*
2 删除链表中重复的结点
3 */
4 public class Solution {
5 public ListNode deleteDuplication(ListNode pHead) {
6 /*
7 构建辅助头结点
8 对于链表而言，不保存的意思也就是跳过这一结点next指向下一个结点
9 */
10 ListNode head=new ListNode(-1);
11 head.next=pHead;
12 ListNode saveHead=head;//保存下来的结点
13 ListNode currentNode=pHead;
14 while(currentNode!=null){
15 if(currentNode.next!=null && currentNode.val==currentNode.next.val) {//有重复了，跳过
16 while (currentNode.next != null && currentNode.val == currentNode.next.val) {
17 currentNode = currentNode.next;//跳过这些相同结点
18 }
19 currentNode=currentNode.next;//有重复，一个都不保存
20 saveHead.next=currentNode;//保存
21 }
22 else {
23 //这里是没重复的
24 saveHead=currentNode;
25 currentNode=currentNode.next;
26 }
27 }
28 return head.next;
29 }
30 }
View Code
三、链表中倒数第K 个结点
1、题目描述
输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k 个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。输入：
{1,2,3,4,5},1
返回值：
{5}
2、解题思路
在链表中：倒数的+顺数的长度等于链表总长度，所以可以设置两个指针，一个先走K 步，剩下的到链表的末尾要走的步数就是倒数第k个节点，需要从头开始走的步数。
1 import java.util.*;
2
3 /*
4 链表中倒数最后k 个结点
5 */
6 public class Solution {
7 public ListNode FindKthToTail (ListNode pHead, int k) {
8 ListNode first = pHead;
9 for(int i = 0; i < k; i++){
10 if(first == null){
11 return first;
12 }
13 first = first.next;
14 }
15 ListNode last = pHead;
16 while(first != null){
17 first = first.next;
18 last = last.next;
19 }
20 return last;
21 }
22 }
View Code
四、链表中环的入口结点
1、题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。输入：
{1,2},{3,4,5}
返回值：
3
说明：
返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3
2、解题思路
使用双指针，一个快指针 fast 每次移动两个节点，一个慢指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。
假设环入口节点为 y1，相遇所在节点为 z1。
假设快指针 fast 在圈内绕了 N 圈，则总路径长度为 x+Ny+(N-1)z。z 为 (N-1) 倍是因为快慢指针最后已经在 z1 节点相遇了，后面就不需要再走了。
而慢指针 slow 总路径长度为 x+y。
因为快指针是慢指针的两倍，因此 x+Ny+(N-1)z = 2(x+y)。
我们要找的是环入口节点 y1，也可以看成寻找长度 x 的值，因此我们先将上面的等值分解为和 x 有关：x=(N-2)y+(N-1)z。
上面的等值没有很强的规律，但是我们可以发现 y+z 就是圆环的总长度，因此我们将上面的等式再分解：x=(N-2)(y+z)+z。这个等式左边是从起点x1 到环入口节点 y1 的长度，而右边是在圆环中走过 (N-2) 圈，再从相遇点 z1 再走过长度为 z 的长度。此时我们可以发现如果让两个指针同时从起点 x1 和相遇点 z1 开始，每次只走过一个距离，那么最后他们会在环入口节点相遇。
1 /*
2 链表中环的入口结点
3 */
4 public class Solution {
5
6 public ListNode EntryNodeOfLoop(ListNode pHead) {
7 if(pHead == null || pHead.next == null){
8 return null;
9 }
10 ListNode slow = pHead;
11 ListNode fast = pHead;
12 do{
13 fast = fast.next.next;
14 slow = slow.next;
15 }while(slow != fast);
16 fast = pHead;
17 while(slow != fast){
18 slow = slow.next;
19 fast = fast.next;
20 }
21 return slow;
22 }
23 }
View Code
五、链表中环的入口结点
1、题目描述
输入一个链表，反转链表后，输出新链表的表头。输入：
{1,2,3}
返回值：
{3,2,1}
2、解题思路
递归
1 /*
2 反转链表
3 */
4 public class Solution {
5 public ListNode ReverseList(ListNode head) {
6 if(head == null || head.next == null){
7 return head;
8 }
9 ListNode next = head.next;
10 // 递归
11 ListNode newHead = ReverseList(next);
12 next.next = head;
13 head.next = null;
14 return newHead;
15 }
16 }
View Code
云想衣裳花想容
春风拂槛露华浓