(资料图)

两两交换链表中的节点(力扣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;    }}

关键词：