代码随想里算法训练营第四天|

标签：ListNode 训练营 curA next 链表 第四天 null 随想 节点

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

第一想法

第一次做这个题的时候其实没搞懂怎么两两交换，原来是12、34、56这样...
应该是反转链表的变体，先判断头节点的next是不是空的，不是空的的话一个指针指向它；后面最大的问题是如何定位“两两”，想不太起来了，现在只能想到两个指针一起向右移

思路&题解

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); //虚拟头结点
        dumyhead.next = head;
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
                temp = cur.next.next.next;
                firstnode = cur.next;
                secondnode = cur.next.next;
                cur.next = secondnode;       
                secondnode.next = firstnode; 
                firstnode.next = temp;     
                cur = firstnode; 
        }
        return dumyhead.next;  
    }
}
//递归没看懂...

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

第一想法

先用一个dummy.next记录头节点，类似于定义一个固定长度为n的滑动窗口滑到最后，窗口右.next=null时，窗口左就是要删除的节点

思路&题解

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode left = dummyNode;
        ListNode right = dummyNode;
        for(int i = 0; i< n ; i++){
            right = right.next;
        }
        while(right.next != null){
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;        
        return dummyNode.next;
    }
}
//很好 第一道能不看题解或思路复现的代码！

  02.07.链表相交 题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

第一想法

只有>-型的相交符合题意？完全没思路，要怎么判断是同一个节点呢...

思路&题解（这题还没太理解，之后再看补一下思路...）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

}

142.环形链表II 题目

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

第一想法

快慢指针，slow右移1步，fast右移2步，因为有环所以一定会在slow进环的第一圈内被fast追上；
为什么返回的是开始入环的节点啊，头痛了起来

思路&题解

public class Solution {
//数学真是神奇啊
    public ListNode detectCycle(ListNode head) {
        ListNode slowIndex = head;
        ListNode fastIndex = head;
        //万一没环肯定是tail.next=null了
        while(fastIndex != null && fastIndex.next != null ){
            slowIndex = slowIndex.next;
            fastIndex = fastIndex.next.next;
            if(slowIndex == fastIndex){//如果有环开始找入环点，这里真妙啊
                ListNode index1 = fastIndex;
                ListNode index2 = head;
                //列方程 路线拆解 就能算出来了
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

文档讲解 https://www.programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html https://www.programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html https://www.programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 视频讲解 https://www.bilibili.com/video/BV1YT411g7br/?spm_id_from=333.788&vd_source=cf378ec519f76396d006e5f8b80218db https://www.bilibili.com/video/BV1vW4y1U7Gf/?spm_id_from=333.788&vd_source=cf378ec519f76396d006e5f8b80218db https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.788&vd_source=cf378ec519f76396d006e5f8b80218db

标签：ListNode,训练营,curA,next,链表,第四天,null,随想,节点
From： https://www.cnblogs.com/bbnltxdy/p/17641688.html