代码随想录第四天| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表II

今天链表致死量

第一题

public static class ListNode {

        int val;

        ListNode next;

        ListNode() {}

        ListNode(int val) { this.val = val; }

        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    }

    public static ListNode swapPairs(ListNode head) {

        if(head==null){

            return head;

        }

        ListNode dummyHead = new ListNode(-1,head);//定义虚拟头结点

        ListNode pre = dummyHead;

        ListNode cur = head;

        ListNode temp = null;

        while (cur!=null&&cur.next!=null){

            pre.next = cur.next;

            temp = cur.next.next;

            cur.next = temp;

            pre.next.next = cur;

            //结束了，已经换过来了

            pre = cur;

            cur = cur.next;

        }

        return dummyHead.next;

    }

算是自己做出来的第一道链表题，其实思路还是挺清晰的，就是三次交换的顺序写的不对，走了些弯路
主要还是借助debug，我慢慢觉得可以理解链表了，加油，今天又是努力爬出垃圾堆的一天！

第二题

 public static ListNode removeNthFromEnd(ListNode head, int n) {

        int len = 0;//链表的长度

        ListNode x = head;

        while (x!=null){

            len ++;

            x = x.next;

        }

        int index = len - n;

        System.out.println(index);

        ListNode dummyHead = new ListNode(-1, head);//虚拟头结点

        ListNode cur = dummyHead;//从虚拟结点开始遍历

        for (int i = 0; i < index; i++) {

            cur = cur.next;

        }

        //此时cur就是要删除的元素的前一个元素

        cur.next = cur.next.next;//删除

        return dummyHead.next;

    }

这题也太简单了叭，我是先一次遍历求出来链表的长度，再遍历来删除
进阶说让用一次遍历，看了题解还是双指针（快慢指针，也不是很难
就这还是中等题，这样的题麻烦再给我来一打，谢

第三题



    public static class ListNode {

        int val;

        ListNode next;

        ListNode(int x) {

            val = x;

            next = null;

        }

    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA==null||headB==null){

            return null;

        }

        int lenA = 0;

        ListNode cur = headA;

        while (cur != null) {

            lenA++;

            cur = cur.next;

        }//链表a的长度

        int lenB = 0;

        cur = headB;

        while (cur != null) {

            lenB++;

            cur = cur.next;

        }//链表b的长度

        if (lenA > lenB) {

            for (int i = 0; i < lenA - lenB; i++) {

                headA = headA.next;

            }

        } else if (lenB > lenA) {

            for (int i = 0; i < lenB - lenA; i++) {

                headB = headB.next;

            }

        }

        //上两步是保证两个链表尾部对齐

        //此时两个指针应该都是指向公共部分的第一个位置

        while (headA != null) {

            if (headA != headB) {

                headA = headA.next;

                headB = headB.next;

            }

            else {

                return headA;

            }

        }

        return null;

    }

这题是今天四题里唯一一道简单题，但我一开始真的卡了蛮久的，主要是不理解为什么下面这图的链表相交点不是1，

真的要看遍了网上所有讲解这题的视频，就发现我是在跟题目抬杠

简单来说，就是求两个链表交点节点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。

后来迷过来之后就发现其实不难，就是找从哪开始这两个链表开始指向同一块区域的
这题没有加虚拟指针，因为如果两个链表的虚拟指针指向的地方都一样的话，他们就是同一个链表啊
我感觉做完这题我对链表的理解就更清晰了。谁是垃圾，平平无奇的链表小天才罢了

第四题

package list;

public class DetectCycle {

    static class ListNode {

        int val;

        ListNode next;

        ListNode(int x) {

            val = x;

            next = null;

        }

    }

    public static ListNode detectCycle(ListNode head) {

        int pos = -1;//标志该链表是否为环形链表

        // 快慢指针判断是否为环形链表

        ListNode fast = head;

        ListNode slow = head;

        while (fast!=null&&fast.next!=null){

            fast = fast.next.next;//快指针一次走两步

            slow = slow.next;//慢指针一次走一步

            if(fast==slow){

                pos = 1;

                break;

            }

        }

        if(pos==-1){

            return null;

        }

        //此时fast和slow指针都指向他们相遇的位

        ListNode indexA = fast;//记录相遇的位置

        ListNode indexB = head;//记录起始的位置

        while (indexA!=indexB){

            indexA = indexA.next;

            indexB = indexB.next;//不相等的时候就各自往下走，总有一个时刻他们会相遇（这莫名的浪漫是怎么回事@_@

        }

        return indexA;

    }

}

这题是今天没有想出来的题，就看了题解思路（午睡前看的），梦里想明白的，晚饭后实现的
突破口就是临界条件，本题涉及两个临界条件：

a）判断是否是环形链表：当快指针与慢指针相遇时，必是环形链表

b）找出环形链表的入口：x = z +(n-1)*(y+z) 【起始点到环形链表入口的距离 = 相遇点到环形链表入口的距离 + 任意个环形链表的长度
这题让我看到算法和数学的不同，数学题是没办法只通过临界条件来求解的

链表总结

我觉得这两天下来基本上把链表的结构掌握的差不多了，我发现我真的爱数据结构，明天的哈希表继续加油
不要害怕，之前老觉得没用过链表做题感觉不会，数组做完停了三天也没开链表，其实多练练就会了，加油吧宝贝
浅浅吐槽一下，链表也太难debug了叭，还有leetcode的这种模式，要想debug还要先还原题目内置的情景

巴特西

代码随想录第四天| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表II

第一题

第二题

第三题

第四题

链表总结

最新文章

热门文章

巴特西

代码随想录第四天| 24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点 、160.链表相交、142.环形链表II

第一题

第二题

第三题

第四题

链表总结

最新文章

热门文章

代码随想录第四天| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表II