代码随想录算法训练营第四天| 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 (面试题) 02.07. 链表相交 142.环形链表II

简介: 代码随想录算法训练营第四天| 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 (面试题) 02.07. 链表相交 142.环形链表II

·今日学习的文章链接和视频链接


代码随想录(programmercarl.com)


·自己看到题目的第一想法

(24. 两两交换链表中的节点)画图看起来挺简单的,但实现的时候很绕。

19.删除链表的倒数第N个节点  )倒叙转为正序,遍历删除节点。

02.07. 链表相交)陷入链表相交的概念之中,题中给出的是一种规则,以此为标准即可。

142.环形链表II )题目没看懂。

  • ·看完代码随想录之后的想法
  • 24. 两两交换链表中的节点)这才是正确的画图姿势(梳理指向逻辑),定义这么多节点且都恰到好处,清晰。


19.删除链表的倒数第N个节点  )双指针很巧妙。


02.07. 链表相交)逻辑比较清晰,实现的步骤及细节繁琐。


142.环形链表II )理解了运转逻辑,看懂了公式推导,

·自己实现过程中遇到哪些困难

24. 两两交换链表中的节点)节点指向还是会乱掉。


19.删除链表的倒数第N个节点  )快指针先移动的长度和n的关系。


02.07. 链表相交)链表长度较大值且怎么指定哪一个比较困难。代码随手关闭了没来的及保存


142.环形链表II )为什么定义双指针?怎么判断是否有环?怎么确定环的位置?这个给问题想清楚了题也就解了

  • ·今日收获,记录一下自己的学习时长
  • 今天最大的收获:敢于自己写代码去实现了,证明有思路慢慢上道了!!!我能高兴一天。

4h


(24. 两两交换链表中的节点)
// 逻辑应该挺清晰的:两个节点为一组进行遍历,之后调整节点指向进行交换位置
// 难点1:清晰指针指向逻辑:虚拟头节点——>第二个节点——>第一个节点
// 难点2:清晰定义多个节点,firNode和secNode代表要交换的两个节点;dumyhead虚拟头节点指向头节点,用于返回结果;temp用于保存要下一轮要遍历的节点;cur用于遍历;
class Solution { 
     public ListNode swapPairs(ListNode head) {
         ListNode dumyhead = new ListNode(-1);
        dumyhead.next = head;
        ListNode cur = dumyhead;
        ListNode firNode;
        ListNode secNode;
        ListNode temp;
        while (cur.next != null && cur.next.next != null) {
            firNode = cur.next;
            secNode = cur.next.next;
            temp = cur.next.next.next;
            cur.next = secNode;
            secNode.next = firNode;
            firNode.next = temp;
            cur = firNode;
        }
        return dumyhead.next;
    }
}


(19.删除链表的倒数第N个节点  )
// 自己写的逻辑:倒叙转成正序,位置从n变为size - n - 1,但没法记录当前节点的前一个节点,存在漏洞。
另外存在疑问:链表不需要判空??
// class Solution {
//     public ListNode removeNthFromEnd(ListNode head, int n) {
//         if (head == null) {
//             return head;
//         }
//         int sz;
//         if (n < 0 || n > sz - 1) {
//             return head;
//         }
//         ListNode dumyhead = head;
//         ListNode cur = dumyhead;
//         for (int i = 0; i < sz - n - 1; i++) {
//             if (cur.next != null && cur.next.next != null) {
//                 cur.next = cur.next.next;
//             }
//         }
//         return dumyhead.next;
//     }
// }
看完代码随想录之后的实现
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1);//-1 和 0 的赋值没什么意义
        dummyHead.next = head;
        ListNode s = dummyHead;
        ListNode f = dummyHead;
        for (int i = 0; i < n; i++) {
            f = f.next;
        }
        while (f.next != null) {
            f = f.next;
            s = s.next;
        }
        s.next = s.next.next;
        return dummyHead.next;
    }
}


(142.环形链表II )
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode f = head;
        ListNode s = head;
        while (f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
            if (s == f) {
                ListNode index1 = f;
                ListNode index2 = head;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
相关文章
|
7天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
13 0
|
7天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
13 2
|
10天前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
1月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
14天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
14天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
19天前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
9 2
|
28天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
23 1
|
14天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】