劍指Offer | day11_雙指針

劍指 Offer 18. 删除連結清單的節點

給定單向連結清單的頭指針和一個要删除的節點的值，定義一個函數删除該節點。

傳回删除後的連結清單的頭節點。

示例 :

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

說明：

• 題目保證連結清單中節點的值互不相同
• 若使用 C 或 C++ 語言，你不需要

  free

  或

  delete

  被删除的節點

方法：雙指針

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
		// 特殊情況
        if(val == head->val) {
            head = head->next;
            return head;
        }
		// 定義快慢指針，快指針指向慢指針的前一位
        ListNode* helper = head;
        ListNode* pre = helper;

		// 周遊連結清單
        while(helper != nullptr) {
            if(helper->val == val) {
                pre->next = helper->next;
                return head;
            }
            pre = helper;
            helper = helper->next;
        }

        return head;
    }
};
           

劍指 Offer 22. 連結清單中倒數第k個節點

給定一個連結清單: 1->2->3->4->5, 和 k = 2.
傳回連結清單 4->5.
           

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        // 快慢指針，快指針比慢指針多走k個數字
        int cnt = 0;
        ListNode* slow = head;
        ListNode* fast = head;
        
        while(fast != NULL) {
            // 快指針先走k位
            if(cnt != k) {
                fast = fast->next;
                cnt++;
            }
            // 快慢指針同步走
            else {
                fast = fast->next;
                slow = slow->next;
            }
        }
        return slow;
    }
};