演算法-鏈表
演算法-鏈表
雲想衣裳花想容，春風拂檻露華濃。
簡介：演算法-鏈表
一、從尾到頭列印鏈表
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、題目描述
輸入：
{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、題目描述
輸入：
{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
雲想衣裳花想容
春風拂檻露華濃
