算法讲解009【入门】单双链表及其反转-堆栈诠释

单双链表及其反转-堆栈诠释 大纲

• 前置知识：无

• 建议：本节内容比较初级，会的同学可以直接跳过

1. 按值传递、按引用传递 （我不知道为什么如此多的同学会犯这种错误，这完全是语言问题）

2. 单链表、双链表的定义

3. 根据反转功能，彻底从系统角度解释链表是如何调整的

4. 链表题目在笔试、面试中的意义就是检验coding能力如何 更难的题目会在【必备】课程里讲述

视频笔记

1. 按值传递、按引用传递 （我不知道为什么如此多的同学会犯这种错误，这完全是语言问题）
1. 值传递：函数的参数是实际值的拷贝。这意味着函数内部对参数的修改不会影响到原始数据，变量和内存都是新的一份
2. 引用传递：函数接收变量的引用（内存地址），使得函数内部对参数的修改能直接反映在原始变量上。 每次都新拷贝了一份，指向同一个内存的新变量
3. 内存区域：堆空间
4. 栈区域：变量空间
5. 实际上 b在栈区域（变量空间），而5在堆空间，而g1(b)，实际上只是创建了个b'
1. g2(b)实际上通过b'找到了内存中的b，改变了b的值

6. 实际上，这里c是变量，而一维数组 {1,2,3,4} 是内存里的东西，g3同样的是传递的是 c' （c' 也指向数组{1,2,3,4}
7. 这里 g4(c)改变了c[0] ，共同改变了内存中的东西
8. 遇到引用传递画图理解
9. // int、long、byte、short // char、float、double、boolean // 还有String // 都是按值传递 int a = 10; f(a); System.out.println(a); // 其他类型按引用传递 // 比如下面的Number是自定义的类 Number b = new Number(5); g1(b); System.out.println(b.val); g2(b); System.out.println(b.val); // 比如下面的一维数组 int[] c = { 1, 2, 3, 4 }; g3(c); System.out.println(c[0]); g4(c); System.out.println(c[0]); } public static void f(int a) { a = 0; } public static class Number { public int val; public Number(int v) { val = v; } } public static void g1(Number b) { b = null; } public static void g2(Number b) { b.val = 6; } public static void g3(int[] c) { c = null; } public static void g4(int[] c) { c[0] = 100; }

2. 单链表、双链表的定义
1. 单链表里头只记录 val 和 next
2. 双链表里头记录 val 和 next 还有last
3. 必有一个 head 节点，一般指向第一个节点

3. 根据反转功能，彻底从系统角度解释链表是如何调整的

1. // 单链表节点 public static class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } // 反转单链表测试链接 : <https://leetcode.cn/problems/reverse-linked-list/> class Solution { public static ListNode reverseList(ListNode head) { ListNode pre = null; ListNode next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } }
2. 首先，head 不为空，head为头节点 ,next指向 1 节点的下一个节点，也就是 2节点 ，接着 pre 是指向空的，于是head.next 头节点的下一个节点也就是 1 节点的下一个节点 也指向空 ，再然后head 指向哪， pred也指向哪里 ，head=next表示head 也指向next（要注意不是赋值或存储），即指向 2 节点 ，然后循环同理









3. head 指向2的时候，初始情况 ，，









4. head指向3的时候，
5. next指向为空时 head->next指向 2 节点，pre=next 即pre指向 3 节点，head=next 即head 也指向为空









6. 最后就跳出循环，然后返回链表就可以了

4. 链表题目在笔试、面试中的意义就是检验coding能力如何 更难的题目会在【必备】课程里讲述

算法讲解010【入门】链表入门题目-合并两个有序链表

链表入门题目-合并两个有序链表

• 前置知识：理解链表及其基本调整

• 建议：做过这个题的同学跳过

• 将两个升序链表合并为一个新的 升序 链表并返回

• 新链表是通过拼接给定的两个链表的所有节点组成的

• 链表题目在笔试、面试中的意义就是检验coding能力如何

• 更难的题目会在【必备】课程里讲述

视频笔记

• 如果有空链表（特殊情况），直接返回另一个

• 创建新链表 head，谁小谁做头head ，相等则 head1 （这里 cur1 <cur2）即 cur1的头节点
• cur1就是做头 head 的下一个节点head->next
• 然后给cur2赋值，但要先判断前面 head == head1 ?吗，不等于那么 cur2=head2，否则cur2=head1
• 接着将 pre 指向 head 节点，即此时的 cur1 前一个节点，也就是相当于做头节点head
• 如图所示

• 开始进入循环，循环条件（两者都不为空）
• 如果 cur1.val<=cur2.val，说明cur1 比较小，将pre.next指向cur1 然后cur1=cur1.next让cur1指向下一个节点
• 否则相反操作
• 走完一轮：
• 每次 if else 判断走完串上一个节点之后，都得改变当前pre节点，指向下一个节点，即pre=pre.next （上面的只是让pre.next=cur1了，并没有改变当前pre节点的位置）
• 直到有一个链表为空，循环结束

• 如果有空了，要将 pre.next 串到剩下的链表里去

• 最后返回 head