(資料圖)

兩兩交換鏈表中的節(jié)點(diǎn)(力扣24.)

• dummyhead .next = head;
• cur = dummyhead;
• while(cur.next!=null&&cur.next.next!=null)
• temp = cur.next;
• temp1=cur.next.next.next;
• cur.next= cur.next.next;
• cur.next.next=temp;
• temp.next=temp1;
• cur = cur.next.next;
• return dummyhead.next;

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode swapPairs(ListNode head) {        //只是用一個temp指針            ListNode dummyHead = new ListNode();            dummyHead.next = head;            ListNode cur = dummyHead;            while(cur.next != null && cur.next.next != null){                //臨時指針存儲cur的next，因?yàn)樵诓僮骱髸兂晒铝⒐?jié)點(diǎn)                ListNode temp = cur.next;                //操作進(jìn)行                cur.next = cur.next.next;                temp.next = cur.next.next;                cur.next.next = temp;                //下一循環(huán)                cur = cur.next.next;            }            return dummyHead.next;    }}

刪除鏈表的倒數(shù)第N個結(jié)點(diǎn)

• 雙指針
• 等距離雙指針刪除鏈表倒數(shù)第N個元素，注意指針應(yīng)該停留在刪除目標(biāo)的前一個元素
• 為實(shí)現(xiàn)上述目標(biāo)可以令快指針先走n+1步且終止條件為fast==null
• 或者快指針先走n步且終止條件為fast.next==null，以下方法使用第二種

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        //雙指針        ListNode dummyHead = new ListNode();        dummyHead.next = head;        ListNode cur = dummyHead;        ListNode post = dummyHead;        while(n > 0){            post = post.next;            if(post == null){                return null;            }            n--;        }        while(post.next != null){            post = post.next;            cur = cur.next;        }        if(cur.next != null){            cur.next = cur.next.next;        }else{            cur.next = null;        }                return dummyHead.next;    }}

面試題：鏈表相交（力扣面試題02.07）

• 簡單來說，就是求兩個鏈表交點(diǎn)節(jié)點(diǎn)的指針。 交點(diǎn)不是數(shù)值相等，而是指針相等。
• 我們求出兩個鏈表的長度，并求出兩個鏈表長度的差值，并令curA為長度更大的一方。然后讓curA移動到，和curB 末尾對齊的位置，然后以此求兩指針是否相同

/** * 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 curA = headA;        ListNode curB = headB;        int lenA = 0;        int lenB = 0;        while(headA != null){            headA = headA.next;            lenA++;        }        while(headB != null){            headB = headB.next;            lenB++;        }        headA = curA;        headB = curB;        if(lenA < lenB){            ListNode temp = headB;            headB = headA;            headA = temp;            int tempInt = 0;            tempInt = lenB;            lenB = lenA;            lenA = tempInt;        }        int gap = lenA - lenB;        while(gap != 0){            headA = headA.next;            gap--;        }        while(headA != null){            if(headA == headB){                return headA;            }            headA = headA.next;            headB = headB.next;        }        return null;    }}

環(huán)形鏈表（力扣142.）

• 判斷鏈表是否有環(huán)
• 返回環(huán)的入口（如果存在）
• 快慢雙指針判斷是否有環(huán)：
• 快指針每次走兩個結(jié)點(diǎn)，慢指針每次走一個結(jié)點(diǎn)
• 快指針對于慢指針的相對速度是每次一個結(jié)點(diǎn)
• 因此快指針和慢指針一定會在環(huán)里相遇
• y + z = 一圈；且y為慢指針在圈內(nèi)走過的距離
• slow = x + y
• fast = x + y + n(y + z)//n為fast多余圈數(shù)
• 又因?yàn)閒ast = 2 * slow
• x + y + n(y+z) = 2(x + y)
• x = n(y + z) - y;
• 其中n應(yīng)該大于等于1
• x = (n - 1)(y + z) + z;
• n=1時，x=z;兩指針會在環(huán)入口相遇
• n!= 1 時，同理
• 即從相遇的地方開始，與起點(diǎn)開始的指針以相同速度移動，最后相遇的點(diǎn)就是入口

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode detectCycle(ListNode head) {        //快慢指針，從快慢指針交界點(diǎn)開始與另一指針從頭節(jié)點(diǎn)開始以相同速度進(jìn)行，交點(diǎn)即為環(huán)入口        ListNode fast = head;        ListNode slow = head;        ListNode target = head;        if(fast == null){            return null;        }        while(fast.next!= null &&fast.next.next !=null){            fast = fast.next.next;            slow = slow.next;            if(fast == slow){                break;            }        }        if(fast.next == null||fast.next.next==null){            return null;        }        while(target != slow){            slow = slow.next;            target = target.next;        }        return target;    }}

關(guān)鍵詞：