(資料圖)

兩兩交換鏈表中的節點(力扣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，因為在操作后會變成孤立節點                ListNode temp = cur.next;                //操作進行                cur.next = cur.next.next;                temp.next = cur.next.next;                cur.next.next = temp;                //下一循環                cur = cur.next.next;            }            return dummyHead.next;    }}

刪除鏈表的倒數第N個結點

• 雙指針
• 等距離雙指針刪除鏈表倒數第N個元素，注意指針應該停留在刪除目標的前一個元素
• 為實現上述目標可以令快指針先走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）

• 簡單來說，就是求兩個鏈表交點節點的指針。 交點不是數值相等，而是指針相等。
• 我們求出兩個鏈表的長度，并求出兩個鏈表長度的差值，并令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;    }}

環形鏈表（力扣142.）

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

/** * 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) {        //快慢指針，從快慢指針交界點開始與另一指針從頭節點開始以相同速度進行，交點即為環入口        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;    }}

關鍵詞：