在链表中遨游
前言:\\textcolor{Green}{前言:}前言:
💞坚持就是胜利💞
链表
- 一、算法介绍
-
- 原理
- 二、算法实例
-
- 1. 题目一:合并两个排序的链表
- 2. 题目二:奇偶链表
- 3. 集大成者:重排链表
- 总结归纳
一、算法介绍
原理
链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针)。
链表的入口节点称为链表的头结点也就是head。
链表分为单链表、双链表、循环链表
- 单链表就是上述部分
- 双链表:每个节点有两个指针域,一个指向上一个节点,一个指向下一个节点。
- 循环链表:在单链表的基础上,将链表的首尾相连。
定义链表:
public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}
这个定义较全。有无参、有参构造
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
二、算法实例
1. 题目一:合并两个排序的链表
题目来源:\\textcolor{blue}{题目来源: }题目来源:合并两个排序的链表
等级:简单\\textcolor{OrangeRed}{等级:简单}等级:简单
推荐原因:很多地方都用到了这个合并排序的方法,一定要记住。
👉题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
限制:0 <= 链表长度 <= 1000
👉代码编写
👉👉方法1
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode res = new ListNode(-1);ListNode tmp = res;while (l1 != null && l2 != null) {if (l1.val > l2.val) {tmp.next = l2;tmp = tmp.next;l2 = l2.next;} else {tmp.next = l1;tmp = tmp.next;l1 = l1.next;}}if (l1 != null) {tmp.next = l1;}if (l2 != null) {tmp.next = l2;}return res.next;}
}
时间复杂度:O(n+m),其中 n
和 m
分别为两个链表的长度。因为每次循环迭代中,l1
和 l2
只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。
空间复杂度:O(1)。我们只需要常数的空间存放若干变量。
👉 注意点
这个是设置了一个头节点,在之后可以较容易的合并链表。只需要维护tmp
指针,同时调整它的next
指针。重复过程直到l1
或l2
指向了 null :当l1
节点的值大于l2
节点的值,那么 tmp
节点接上 l2
节点的值,反之就接 l1
节点的值。
在循环终止的时候, l1
和 l2
至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。意味着我们只需要将非空链表接在合并链表的后面,并返回合并链表即可。也就是说最后再判断还有哪一个指针没有合并,将其接在 tmp
的后面即可。
2. 题目二:奇偶链表
题目来源:\\textcolor{blue}{题目来源: }题目来源: 奇偶链表
等级:中等\\textcolor{OrangeRed}{等级:中等}等级:中等
👉题目描述
给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1)
的额外空间复杂度和 O(n)
的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
提示:
n == 链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106
👉代码编写
👉👉方法1
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode oddEvenList(ListNode head) {if (head == null) {return head;}ListNode odd = head;ListNode evenhead = head.next, even = evenhead;while (even != null && even.next != null) {odd.next = even.next;odd = odd.next;even.next = odd.next;even = even.next;}odd.next = evenhead;return head;}
}
时间复杂度:O(n),其中 n 是链表的节点数。需要遍历链表中的每个节点,并更新指针。
空间复杂度:O(1)。只需要维护有限的指针。
👉 注意点
这个题目主要是学习这个思维,并且题目中明确要求我们要使用 O(1)
的额外空间复杂度和 O(n)
的时间复杂度下解决这个问题。
所以我们只能使用若干个临时变量。并且遍历链表只能进行一次。
一个链表拆成两个链表—>去维护。
在题目中我们要维护两个指针。一个是指向奇数节点的 odd
,一个是指向偶数节点的 even
。链表的头节点是 head
,也是奇数节点的头节点。那么evenHead
是偶数链表的头节点。
更新链表:
- 奇数节点:odd.next=even.nextodd.next = even.nextodd.next=even.next 。奇数节点的后一个节点要指向偶数节点的下一个节点。然后将 odd=odd.nextodd = odd.nextodd=odd.next 这样的话
odd
就变成了偶数节点的下一个节点。 - 偶数节点:even.next=odd.nexteven.next = odd.nexteven.next=odd.next 。偶数节点的后一个节点是奇数节点的下一个节点。然后将 even=even.nexteven = even.nexteven=even.next 这个时候的
even
就变成了odd
的下一个节点。
直到: even == null && even.next == null
就跳出去。最后将奇数链表的尾部连接上偶数链表的头部,也就是 odd.next=evenHeadodd.next = evenHeadodd.next=evenHead
3. 集大成者:重排链表
题目来源:\\textcolor{blue}{题目来源: }题目来源: 重排链表
等级:中等\\textcolor{OrangeRed}{等级:中等}等级:中等
为什么说这个题目是集大成者
里面包含着:
- 找到链表中点(快慢指针)
- 反转链表
- 合并链表
你就说美不美吧,一个题目学会三种方式
👉题目描述
给定一个单链表 L 的头节点 head ,单链表 L 表示为:
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[1,4,2,3]
示例 2:
输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]
提示:
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
👉代码编写
👉👉方法1
第一种方法是:将链表转换成数组,然后修改完后再重建链表。这个方法不推荐。这个代码引用了官方:
class Solution {public void reorderList(ListNode head) {if (head == null) {return;}List<ListNode> list = new ArrayList<ListNode>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;if (i == j) {break;}list.get(j).next = list.get(i);j--;}list.get(i).next = null;}
}
复杂度分析
时间复杂度:O(N),其中 N 是链表中的节点数。
空间复杂度:O(N),其中 N 是链表中的节点数。主要为线性表的开销。
👉👉方法2
观看题目描述,可以看到,最终想要的结果就是将原来链表的左半部分
和反转后的后半部分
合并
那么方法就来了。找到链表中点—>反转后半部分—>合并链表
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public void reorderList(ListNode head) {if (head == null) {return;}ListNode mid = middleNode(head);ListNode l1 = head;ListNode l2 = mid.next;mid.next = null;l2 = reverseList(l2);mergeList(l1, l2);}// 找到链表的中点public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}public ListNode reverseList(ListNode l2) {ListNode pre = null;ListNode cur = l2;ListNode tmp = null;while (cur != null) {tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}public void mergeList(ListNode l1, ListNode l2) {ListNode l1_tmp;ListNode l2_tmp;while (l1 != null && l2 != null) {l1_tmp = l1.next;l2_tmp = l2.next;l1.next = l2;l1 = l1_tmp;l2.next = l1;l2 = l2_tmp;}}
}
👉 注意点
这个合并和第一题的合并不是一回事。这个不需要我们对比两个节点的值。而是你一个我一个。
时间复杂度:O(N),其中 N 是链表中的节点数。
空间复杂度:O(1)。
总结归纳
链表的题目一定要动手画图会更加容易理解。