代码随想录第四天|力扣24.两两交换链表节点、力扣19.删除链表的倒数第N个结点、力扣面试02.07链表相交、力扣142.环形链表

手机

英国房地产因利率上升陷入困境房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

代码随想录第四天|力扣24.两两交换链表节点、力扣19.删除链表的倒数第N个结点、力扣面试02.07链表相交、力扣142.环形链表

2023-07-31 05:54:14 来源：博客园

(相关资料图)

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

关键词：