算法刷题打卡day3

[DBW666888]

24.两两交换链表中的节点

题目描述：

解题思路：

这道题依旧使用了虚拟头节点，交换前每次指针cur指向待交换两个节点的前一个节点。每次交换前先用临时变量保存第一个节点和第三个节点，然后依次如下修改指针：cur.next指向第二个节点，第二个节点的next指向第一个节点，第一个节点的next指向第三个节点，拉直后发现一对节点就已经交换成功了。交换完成后cur移动到下一对节点的前一个位置（即cur = cur.next.next），循环直到剩余节点不足一对，奇数个节点则最后一个无需改变。

代码：

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyhead=new ListNode();
        dummyhead.next=head;
        ListNode cur=dummyhead;

        ListNode temp1;
        ListNode temp2;
        while(cur.next!=null && cur.next.next!=null){
            temp1=cur.next;
            temp2=cur.next.next.next;
            cur.next=cur.next.next;
            cur.next.next=temp1;
            temp1.next=temp2;
            cur=cur.next.next;
        }
        return dummyhead.next;
    }
}

19.删除链表的倒数第N个节点

题目描述：

解题思路：

这道题使用了快慢双指针的方法，这种方法就无需纠结链表的长度问题了。这道题的具体用法是先让快指针从虚拟头节点出发走n+1步，此时快慢指针相距n+1。然后同时移动快慢指针，当快指针为null时，慢指针正好指向待删除节点的前一个节点。最后执行删除操作（slow.next = slow.next.next），返回虚拟头节点的下一个节点即可。

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyhead=new ListNode();
        dummyhead.next=head;
        ListNode fast=dummyhead;
        ListNode slow=dummyhead;

        for(int i=0;i<=n;i++){
            fast=fast.next;
        }

        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;

        return dummyhead.next;
    } 
}

02.07.链表相交

题目描述：

解题思路：

这道题我完全是自己想出来的。先用两个节点分别遍历两个链表得到各自的长度，但此时无法确定那条链表更长，于是就用交换的方法确保len1长于len2，长度差为len1-len2。然后让较长的链表先移动len1-len2步，前面len1-len2个节点直接删除，这样两个链表剩余部分的长度就相等了。接着同时遍历两个链表，比较当前节点是否相同，不相同就同速往后遍历，遇到的第一个相同的节点即为交点。核心思想就是通过对齐尾部来消除长度差异。

代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1=headA;
        ListNode p2=headB;
        int len1=0;
        int len2=0;
        while(p1 != null){
            len1++;
            p1=p1.next;
        }
        while(p2 != null){
            len2++;
            p2=p2.next;
        }

        p1=headA;
        p2=headB;
        if(len2 > len1){
            int tempLen=len1;
            len1=len2;
            len2=tempLen;

            ListNode tempNode=p1;
            p1=p2;
            p2=tempNode;
        }

        for(int i=0;i<len1-len2;i++){
            p1=p1.next;
        }
        while(p1 != p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1==p2?p1:null;
    }
}

142.环形链表II

题目描述：

解题思路：

这道题依旧使用快慢指针的方法来判断是否有环。核心思想就是让快指针每次走两步，慢指针每次走一步。同时利用数学方法证明，若相遇则说明有环，快慢指针一定会在第一圈后就相遇并且相遇点和开始点到环入口的距离是相等的。于是让一个指针从头节点出发，另一个指针从相遇点出发，两者以相同速度前进，再次相遇的位置即为环的入口节点。

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode node1;
        ListNode node2;
        while(fast != null && fast.next != null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast == slow){
                node1=head;
                node2=fast;
                while(node1 != node2){
                    node1=node1.next;
                    node2=node2.next;
                }
                return node1;
            }
        }
        return null;
    }
}