代碼隨想錄算法訓(xùn)練營第四天: 24.兩兩交換鏈表中的節(jié)點 19.刪除鏈表的倒數(shù)第N個節(jié)點 160(面試題).鏈表相交 142.環(huán)形鏈表II

24.兩兩交換鏈表中的節(jié)點

要點 : 把要操作的節(jié)點單獨用指針標(biāo)出來, 思路會更清晰

class Solution {
    public ListNode swapPairs(ListNode head) {
        //普通方法
        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            cur.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}

遞歸 :

第一步 : 假設(shè)后面已經(jīng)處理好,如何處理當(dāng)前節(jié)點

第二步 : 分析什么條件下終止

第三步 : 標(biāo)出有關(guān)返回值的操作節(jié)點如head , head.next ; 后面一團看作整體標(biāo)出返回值對應(yīng)節(jié)點,逐步分析操作

class Solution {
    public ListNode swapPairs(ListNode head) {
        //遞歸
        if(head == null || head.next == null){
            return head;
        }

        head.next.next = swapPairs(head.next.next);
        ListNode temp = head.next;
        head.next = head.next.next;
        temp.next = head;
        head = temp;
        return head;
    }
}

19.刪除鏈表的倒數(shù)第N個節(jié)點

雙指針:利用相對位置 , 得到倒數(shù)第n個節(jié)點的前一個節(jié)點的位置

屢次犯錯 : 有dummy的返回不是head而是dummy.next

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i = 0; i <= n; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        //注意判斷空指針
        if(slow.next != null){
        slow.next = slow.next.next;
        }
        return dummy.next;
    }
}

160(面試題).鏈表相交

• 假設(shè)鏈表A的長度為a，鏈表B的長度為b，相交部分的長度為c。
• 指針p1走過的總路徑長度為a + (b - c)，指針p2走過的總路徑長度為b + (a - c)。
• 由于a + (b - c) = b + (a - c)，兩個指針最終會在相交節(jié)點相遇。
• 若不相交, c = 0, 則總路徑為 a + b, 即會在null相遇

(版本二) 合并鏈表實現(xiàn)同步移動
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// p1 指向 A 鏈表頭結(jié)點，p2 指向 B 鏈表頭結(jié)點
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 鏈表末尾，轉(zhuǎn)到 B 鏈表
			if (p1 == null) p1 = headB;
			else            p1 = p1.next;
			// p2 走一步，如果走到 B 鏈表末尾，轉(zhuǎn)到 A 鏈表
			if (p2 == null) p2 = headA;
			else            p2 = p2.next;
		}
		return p1;
    }
}

142.環(huán)形鏈表II

兩個問題 : 是否有環(huán) and 入口在哪

**是否有環(huán) : **快慢指針法 : 快指針和慢指針一定會在環(huán)中相遇

**入口在哪 : **根據(jù)公式 (x + y) * 2 = x + y + n (y + z) 可以得出 x = (n - 1) (y + z) + z

? 說明如果有關(guān)指針從頭出發(fā),另一個指針從相遇的位置出發(fā) , 他們一定會在入口相遇

public class Solution {
    public ListNode detectCycle(ListNode head) {
    
        ListNode fast = head, slow = head;
        
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode p1 = head;
                ListNode p2 = fast;

                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                }
                return p1;
            }
        }
        return null;
    }
}