LeetCode 鏈表題 ( Java )

leetcode 237. 刪除鏈表中的節點

鏈接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

示例 :

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節點，那麼在調用了你的函數之後，該鏈表應變為 4 -> 1 -> 9.

 這道題比較簡單，修改之前節點的 next 指針，使其指向之後的節點：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

leetcode 160. 相交鏈表

鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

編寫一個程式，找到兩個單鏈表相交的起始節點。

如下麵的兩個鏈表：

在節點 c1 開始相交。要求返回 c1 這個節點。

先得到兩條鏈表的長度差 offset，再將長鏈表跳過 offset 個節點，然後再讓這兩個鏈表輪流逐個遍歷節點，直到相遇。

比如上圖 A 和 B 差一個長度差為 1，先跳過 b1 這個結點到達 b2，然後 A 開始從 a1 遍歷，到達 a2， B 到達 b3； 隨後 A 到達 c1，B 到達 c1，兩點相遇，返回 c1. 

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;

        int lengthA = getListLength(headA);
        int lengthB = getListLength(headB);
        ListNode longList = headA;
        ListNode shortList = headB;
        int offset = Math.abs(lengthA - lengthB);
        if(lengthA < lengthB){
            longList = headB;
            shortList = headA;
        }
        for(int i=0; i < offset; i++){
            longList = longList.next;
        }
        while(shortList != longList){
            shortList = shortList.next;
            longList = longList.next;
        }
        return shortList;
    }
    public int getListLength(ListNode p){
        int length = 0;
        while(p != null){
            length++;
            p = p.next;
        }
        return length;
    }
}

我又看了這道題的題解，看到有其他解法：兩條鏈表先遍歷一輪（消除長度差），當鏈表到達結尾的時候，反而讓到達鏈表末尾的節點指向另一個鏈表的頭部，然後再接著遍歷，這樣就消除了兩條鏈表的長度差，可以大致理解為：兩個人以同樣的速度跑步，跑的路程也一致，那麼肯定會同一個時間點到達終點。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

leetcode 206. 反轉鏈表

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

 此題的思路是逐個反轉，先變成 NULL<-1  2->3->4->5->NULL; 然後是 1<-2  3->4->5->NULL; 接著是 1<-2<-3  4->5->NULL，以此類推。那麼我們首先就要先創建一個空節點為 prev，使得 1 指向它，但是，需要先把 2 這個節點保存起來，不然當 1 指向 NULL 後就失去了 2 以後的數據。完成第一次反轉後就一直迭代下去。可能表達得不太行，看代碼吧：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = prev;           // 翻轉
            
            prev = head;
            head = next;
        }
        return prev;
    }
}

如果文字解釋看不懂，代碼也看不懂，那就視頻吧，推薦這個小姐姐講的   用Java解決翻轉鏈表 Leetcode206 Reverse Linked List 

leetcode 141. 環形鏈表

給定一個鏈表，判斷鏈表中是否有環。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

（1） 哈希

 　遇到這種類型得題目一般大部分都是用 hash ，通過遍歷把每個節點存起來，如果該節點後續還被訪問到，則表示該鏈表為環形鏈表。

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodes = new HashSet<>();
    while (head != null) {
        if (nodes.contains(head)) {
            return true;
        } else {
            nodes.add(head);
        }
        head = head.next;
    }
    return false;
}

（2）雙指針

　定義兩個指針，從 head 開始，慢指針移動一步，快指針移動兩步，如果兩個指針相遇則為環形鏈表，否則不是。這個道理就跟兩個不同速度的人在同一條跑道上跑步一樣，如果是環形的總會相遇。

public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null) {
            if (slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

 leetcode 19. 刪除鏈表的倒數第N個節點

給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數第二個節點後，鏈表變為 1->2->3->5.

（1）第一種方法：由於不清楚鏈表的長度，因此可以先遍歷鏈表得到其長度，然後第二次遍歷將倒數第N個節點刪除，即被刪除節點的前一個節點指向刪除節點的後一個節點：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode list = head;
    while (list != null) {
        length++;
        list = list.next;
    }
    length -= n;
    list = dummy;
    while (length > 0) {
        length--;
        list = list.next;
    }
    list.next = list.next.next;
    return dummy.next;
}

（2）第二種方法：使用雙指針，先讓其中一個指針走 N+1 步，然後兩個指針同時移動，到達被刪除節點的前一個節點時把它刪除：

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        ListNode q = dummy;
        for (int i = 0; i <= n; i++) {
            q = q.next;
        }
        while (q != null) {
            p = p.next;
            q = q.next;
        }
        p.next = p.next.next;
        return dummy.next;
   }