劍指offer-之-鏈表

6. 從尾到頭列印鏈表 難度：簡單

本題要求從尾到頭列印鏈表，輸出格式為陣列，我們可以通過遞回到鏈表的最后一位再回溯將鏈表的節點值加入ArrayList中，再將它轉化為陣列即可，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        cur(head);
        int[] res = new int[list.size()];
        for(int i = 0;i<list.size();++i){
            res[i] = list.get(i);
        }
        return res;
    }
    public void cur(ListNode node){
        if(node == null)    return;
        cur(node.next);
        list.add(node.val);
    }
}

25. 合并兩個有序的鏈表 難度 ：簡單

本題是合并兩個有序的鏈表，那么我們用兩個指標分別遍歷兩個鏈表再比較節點的值來連成一個新的鏈表即可，需要注意的地方是當一個鏈表被遍歷完之后，另外一個鏈表可能還沒有遍歷完，那么我們在回圈結束之后將鏈表中沒遍歷完的部分直接加入新的鏈表后面即可（沒遍歷完的部分就是兩個鏈表中最大的部分），

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                
                cur.next = l1;
                l1=l1.next;
            }else{
                
                cur.next = l2;
                l2=l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 == null)?l2:l1;
        return newHead.next;
    }
}

22.鏈表中倒數第k個節點 難度：簡單

本題用快慢節點的方法來解決，首先定義兩個節點fast和slow，題目中求倒數第k個節點，我們只需要讓fast節點先走k-1步，再讓兩個節點同時往后走，當fast節點走到最后一個節點時，slow節點指向的就是我們要的倒數第k個節點，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(k <= 0)  return null;
        ListNode slow = head;
        ListNode fast = head;
        while(k>1){
            fast = fast.next;
            k--;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

24.反轉鏈表 難度：簡單

本題方法是在遍歷原鏈表的同時將其每個節點用頭插法的方式插入我們構造的新的頭結點中，最后回傳新的頭結點就完成了鏈表的反轉操作，

/**
 * 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 newHead = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            ListNode nextNode = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = nextNode;
        }
        return newHead.next;
    }
}

18. 洗掉鏈表的節點 難度：簡單

本題要求洗掉鏈表中的一個節點，那么我們只需創建一個定位節點和它的前驅節點即可，當定位節點的值等于val時，讓pre.next = cur.next;即可，問題在于我們要洗掉的節點可能是該鏈表的頭結點，此時可以直接處理，也可以新定義一個頭結點來指向該鏈表，讓原鏈表的頭結點成為第二個節點，那么就不需要進行特殊處理，本題定義新的頭結點來實作，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null)    return null;
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode cur = head;
        ListNode pre = newHead;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }
            pre = cur;
            cur = cur.next;
        }
        return newHead.next;
    }
}

35.復雜鏈表的復制 難度：中等

本題核心：哈希表，用哈希表來存原鏈表的每個節點和新鏈表的每個節點，兩者是一一對應的關系，我們先存盤只帶有val的每一個新節點，那么哈希表中存盤的每一個舊節點和每一個新節點都是key-value的關系，接下來就是通過這種關系讓新節點的next和random指向正確的節點，最后回傳新節點的頭結點即可，

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)    return null;
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

52. 兩個鏈表的第一個公共節點 難度：簡單

本題用雙指標解法：我們設node為公共節點，鏈表headA的長度為A，鏈表headB的長度為B，兩鏈表的公共部分長度為C，那么：

從headA到node的長度為：A-C

從headB到node的長度為：B-C

當指標a走完鏈表headA再走鏈表headB到node節點時一共走了：A+(B-C);

當指標b走完鏈表headB再走鏈表headA到node節點時一共走了：B+(A-C);

可以看出A+(B-C) = B+(A-C);

因此當指標a和b相遇時，他們走的節點個數相同，結果就顯而易見了，

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while(a != b){
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
}