雙指針專項練習-----連結清單操作

一、雙指針法

快慢指針的思想。我們将第一個指針 fast 指向連結清單的第k+1 個節點，第二個指針 slow 指向連結清單的第一個節點，此時指針fast 與 slow 二者之間剛好間隔 k 個節點。此時兩個指針同步向後走，當第一個指針fast 走到連結清單的尾部空節點時，則此時slow 指針剛好指向連結清單的倒數第k個節點。

1.1 連結清單中倒數第k個節點

public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
    // 快指針 指向k+1
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        // 快慢指針同時走，快指針指向null的時候，傳回slow
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;      

1.2 删除連結清單倒數第N個節點

public ListNode removeNthFromEnd(ListNode head, int n) {
        // 增加頭結點
        ListNode dummy = new ListNode(0,head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 0; i < length - n + 1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        // 删除頭結點
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head){
        int length = 0;
        while (head!=null){
            ++length;
            head = head.next;
        }
        return length;
    }