大佬教程收集整理的这篇文章主要介绍了LeetCode通关：听说链表是门槛，这就抬脚跨门而入，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
刷题路线参考：https://github.com/youngyangyang04/leetcode-master
https://github.com/chefyuan/algorithm-base
链表是一种链式存储的线性表c;不要求逻辑上相邻的数据元素在物理位置上也相邻。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的引用。也可以称之为数据域和指针域。
入口节点称为头结点c;最后一个节点指向null。
如图所示：
每个节点除了有指向下一个节点的引用c;还有指向上一个节点的引用。
双链表除了可以从前往后遍历c;还可以从后往前遍历。
循环链表c;就是最后一个节点的后继指向头结点c;头节点的前驱指向最后一个节点。
我们知道链表在内存中不是连续分配的。链表是通过指针域的指针链接内存中的各个节点。
所以链表在内存中是散乱分布在内存中的某地址上c;分配机制取决于操作系统的内存管理。
链表的定义主要包含两个部分：数据域和指针域。
在Java中因为屏蔽了指针的存在c;我们的定义可以是数据c;后继/前驱节点。
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
@H_616_128@ public class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(int x) { val = x; }
}
@H_616_128@我们以单链表为例c;来看一下链表的一些基本操作：
@H_780_197@
图中的插入和删除的时间复杂度都为O(1)@H_616_128@。但是需要注意c;这里的情况是插入和删除已经知道前趋节点的情况。
如果c;还需要检索相应的节点c;那么时间复杂度是O(n)@H_616_128@。
ɡ5; 题目：203. 移除链表元素 (https://leetcode-cn.com/problems/remove-linked-list-elements/)
❓ 难度：简单
Ὅ5; 描述：给你一个链表的头节点 head@H_616_128@ 和一个整数 val@H_616_128@ c;请你删除链表中所有满足 Node.val == val@H_616_128@ 的节点c;并返回 新的头节点 。
💡 思路：
我们来看一下代码实现：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 203. 移除链表元素
* @author 三分恶
* @date 2021/7/25 10:08
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode cur = head;
ListNode prev = head;
while (cur != null) {
ListNode temp = cur.next;
//删除节点
if (cur.val == val) {
//头节点
if (cur == head) {
head = temp;
}
//非头节点
if (cur != head) {
prev.next = cur.next;
}
} else {
prev = cur;
}
cur = temp;
}
return head;
}
@H_616_128@⏰ 时间复杂度：O(n)。
🏠 空间复杂度：O(1)。
💡 思路：
可以设置一个虚拟的头指针c;让它的next指向头节点c;这样头节点的删除就和普通节点是一致的了。
代码如下：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 203. 移除链表元素
* @author 三分恶
* @date 2021/7/25 10:08
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
//虚拟头节点
ListNode dummy = new ListNode(-1, head);
ListNode prev = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
return dummy.next;
}
@H_616_128@🚗 时间复杂度：O(n)。
🏠 空间复杂度：O(1)。
ɡ5; 题目：707. 设计链表 (https://leetcode-cn.com/problems/design-linked-list/)
❓ 难度：中等
Ὅ5; 描述：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值c;next 是指向下一个节点的指针/引用。如果要使用双向链表c;则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
示例：
@H_23_91@myLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addATindex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteATindex(1); //现在链表是1-> 3 linkedList.get(1); //返回3 @H_616_128@
提示：
💡 思路：
这是一道大题。
链表基本操作的图示在前面已经给出了。
比较简练的方式是设置一个伪头节点c;保证链表永不为空c;这样操作起来会方便很多。
但是c;我本人看过一点Java链表的代码c;所以不想采用这种方式。
PS：这里踩了一个坑c;没仔细审题c;链表index是从0开始的c;导致思考5分钟c;AC两小时。
/**
* @Author: 三分恶
* @Date: 2021/7/25
* @Description: 707. 设计链表
* https://leetcode-cn.com/problems/design-linked-list/
* <p>
* 链表界节点是 0——index
**/
public class @H_948_96@myLinkedList {
//链表元素的个数
int size;
//头结点
ListNode head;
/**
* 初始化链表
*/
public @H_948_96@myLinkedList() {
size = 0;
}
/**
* 获取第index个节点的数值
*/
public int get(int index) {
//非法参数
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
/**
* 在链表最前面插入一个节点
*/
public void addAtHead(int val) {
addATindex(0, val);
}
/**
* 在链表的最后插入一个节点
*/
public void addAtTail(int val) {
addATindex(size, val);
}
/**
* 在第 index 个节点之前插入一个新节点c;例如index为0c;那么新插入的节点为链表的新头节点。
* 如果 index 等于链表的长度c;则说明是新插入的节点为链表的尾结点
* 如果 index 大于链表的长度c;则返回空
*/
public void addATindex(int index, int val) {
//非法参数
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
//如果链表为空c;直接作为头节点
if (size == 0) {
head = new ListNode(val);
size++;
return;
}
//插入
size++;
ListNode addNode = new ListNode(val);
//插入头节点之前
if (index == 0) {
addNode.next = head;
head = addNode;
return;
}
//找到前驱节点
ListNode pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
addNode.next = pre.next;
pre.next = addNode;
}
/**
* 删除第index个节点
*/
public void deleteATindex(int index) {
if (index < 0 || index > size-1) {
return;
}
size--;
//头节点
if (index == 0) {
head = head.next;
return;
}
//非头节点
ListNode prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
//删除节点
prev.next = prev.next.next;
}
}
@H_616_128@⏰时间复杂度：
🏠空间复杂度：所有的操作都是 O(1)。
ɡ5; 题目：剑指 Offer 22. 链表中倒数第k个节点 (https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
❓ 难度：简单
Ὅ5; 描述：输入一个链表c;输出该链表中倒数第k个节点。为了符合大多数人的习惯c;本题从1开始计数c;即链表的尾节点是倒数第1个节点。
例如c;一个链表有 6 个节点c;从头节点开始c;它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
💡 思路：
这道题可以用双指针的办法。
以示例说明c;一个指针pre@H_616_128@在前c;先跑1步c;一个指针after@H_616_128@在后c;跟着跑c;pre到头的时候c;刚好afer是倒数第二个。
代码实现：
/**
* 剑指 Offer 22. 链表中倒数第k个节点
*
* @param head
* @param k
* @return
*/
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode preNode = head, afterNode = head;
int step = 0;
while (preNode!=null) {
preNode = preNode.next;
step++;
if (step > k) {
afterNode = afterNode.next;
}
}
return afterNode;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：876. 链表的中间结点 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)
❓ 难度：简单
Ὅ5; 描述：给定一个头结点为 head@H_616_128@ 的非空单链表c;返回链表的中间结点。
如果有两个中间结点c;则返回第二个中间结点。
💡 思路：
和上一道题有点类似。
上一道题是两个指针分先、后。
这道题可以两个指针分快@H_616_128@、慢@H_616_128@。
一示例1为例c;fast@H_616_128@指针跑两步c;slow@H_616_128@指针跑一步c;fast@H_616_128@指针恰好跑的是slow@H_616_128@的两倍c;fast@H_616_128@指针跑到头了c;slow@H_616_128@指针不就恰好跑到中间了嘛！
代码如下：
/**
* 876. 链表的中间结点
*
* @param head
* @return
*/
public ListNode @H_354_263@middleNode(ListNode head) {
if (head == null) {
return null;
}
//定义快慢指针
ListNode fastNode = head, slowNode = head;
while (fastNode != null && fastNode.next != null) {
//快指针走两步
fastNode = fastNode.next.next;
//慢指针走一步
slowNode = slowNode.next;
}
return slowNode;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：19. 删除链表的倒数第 N 个结点 (https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
❓ 难度：中等
Ὅ5; 描述：给你一个链表c;删除链表的倒数第 n@H_616_128@ 个结点c;并且返回链表的头结点。
💡 思路：
这道题上手是不是就觉得很熟？
这是 203.移除链表元素@H_616_128@ 和 剑指 Offer 22. 链表中倒数第k个节点@H_616_128@的结合。
那么解法c;我们同样可以结合这两道题。
代码如下：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 19. 删除链表的倒数第 N 个结点
* @author 三分恶
* @date 2021/7/25 17:17
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
//快慢指针
ListNode fast = head, slow = head;
//虚拟头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
//一个指针从虚拟头节点开始跑
ListNode preSlow = dummy;
//计算步数
int step = 0;
while (fast != null) {
//fast先走n步
fast = fast.next;
step++;
//slow开始移动
if (step > n) {
slow = slow.next;
preSlow = preSlow.next;
}
}
//找到倒数第n个节点c;和它的前驱
preSlow.next = slow.next;
return dummy.next;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：876. 链表的中间结点 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)
❓ 难度：简单
Ὅ5; 描述：给定一个头结点为 head@H_616_128@ 的非空单链表c;返回链表的中间结点。
如果有两个中间结点c;则返回第二个中间结点。
💡 思路：
他们都说这道题浪漫c;我却不想听什么狗屁的浪漫爱情故事c;我只想搞钱。
这道题可以用双指针解决c;定义两个指针c;当某一指针遍历完链表之后c;然后掉头去另一个链表的头部c;继续遍历。因为速度相同所以他们第二次遍历的时候肯定会相遇。
代码实现：
/**
* 剑指 Offer 52. 两个链表的第一个公共节点
*
* @param headA
* @param headB
* @return
*/
public ListNode geTintersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
//定义两个节点
ListNode nodeA = headA, nodeB = headB;
while (nodeA != nodeB) {
//没到头就后移c;到头c;就指向另一树头结点
if (nodeA != null) {
nodeA = nodeA.next;
} else {
nodeA = headB;
}
//另一个节点也一样
if (nodeB != null) {
nodeB = nodeB.next;
} else {
nodeB = headA;
}
}
return nodeA;
}
@H_616_128@⏰ 时间复杂度：O(m+n)c;R_555_11845@和n分别为两个链表的长度。
160. 相交链表 、面试题 02.07. 链表相交 和这道题基本是一模一样的。
ɡ5; 题目：206. 反转链表 (https://leetcode-cn.com/problems/reverse-linked-list/)
❓ 难度：简单
Ὅ5; 描述：给你单链表的头节点 head@H_616_128@ c;请你反转链表c;并返回反转后的链表。
💡 思路：
这是一道非常经典的题目。翻转怎么做呢？
遍历链表c;将当前节点的后继指向当前。
在这里我们要额外引入两个指针：
prev@H_616_128@表示前趋c;用于反转时候后继的指向。temp@H_616_128@用于临时存储下一个节点c;这个temp是用来干什么的？用来遍历c;因为反转之后c;原来的next节点已经指向prev了。说真的c;作为一个C语言菜鸡c;我又想起了被指针数组@H_616_128@、数组指针@H_616_128@支配的日子c;所以我画了一个作为Java程序员理解的示意图c;如有不当之处c;请指出。
也找到了一张动图（参考[1])：
代码如下：
/**
* 206. 反转链表
*
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
//保存下一个节点
ListNode temp = current.next;
//修改当前节点后继指向
current.next = prev;
//修改前趋节点
prev = current;
current = temp;
}
return prev;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：92. 反转链表 II (https://leetcode-cn.com/problems/reverse-linked-list-ii/)
❓ 难度：中等
Ὅ5; 描述：给你单链表的头指针 head 和两个整数 left 和 right c;其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点c;返回 反转后的链表 。
💡 思路：
反转链表经常容易忘c;我们再做一道进阶的题目来巩固一下。
这道题什么思路呢？
我们可以把反转的这一部分拆出来c;作为新的链表c;反转新链表c;然后再和前后的节点重新连接。
代码实现：
/**
* @return ListNode
* @Description: 92. 反转链表 II
* @author 三分恶
* @date 2021/7/24 0:32
*/
public ListNode reversebetween(ListNode head, int left, int right) {
//虚拟头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
//一、获取被截取的子链表的前、后节点
//移动到左节点前一个节点
int i = 0;
for (; i < left - 1; i++) {
cur = cur.next;
}
//保存左节点的前一个节点
ListNode leftPre = cur;
//移动到right节点
for (; i < right; i++) {
cur = cur.next;
}
//保存右节点的后一个节点
ListNode rightAfter = cur.next;
//二、截取子链表
//切断右节点后的部分
cur.next = null;
//左节点作为子链表头节点
ListNode sonHead = leftPre.next;
//切断左节点前的部分
leftPre.next = null;
//三、反转子链表
ListNode rNode = reverseList(sonHead);
//四：重新连接
leftPre.next = rNode;
sonHead.next = rightAfter;
return dummy.next;
}
/**
* @return ListNode
* @Description: 反转链表
* @author 三分恶
* @date 2021/7/25 10:06
*/
ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：234. 回文链表(https://leetcode-cn.com/problems/palindrome-linked-list/)
❓ 难度：简单
Ὅ5; 描述：请判断一个链表是否为回文链表。
💡 思路：
要是双向链表就好了c;直接一个指针从头到尾c;一个指针从尾到头c;但是这是一个单链表。
所以我们可以用一个列表先把之给存起来c;再用双指针分别从两头遍历比较。
代码如下：
/**
* 234. 回文链表
* 将值复制到集合
*
* @param head
* @return
*/
public Boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
List<Integer> nodes = new ArrayList<>(16);
//将链表的值放入集合
while (head != null) {
nodes.add(head.val);
head = head.next;
}
//双向遍历集合
int start = 0, end = nodes.size() - 1;
while (start < end) {
if (!nodes.get(start).equals(nodes.get(end))) {
return false;
}
start++;
end--;
}
return true;
}
@H_616_128@⏰ 时间复杂度：O(n)c;其中 n 指的是链表的元素个数c;。
🏠 空间复杂度：O(n)c;其中 n 指的是链表的元素个数c;因为我们用了一个ArrayList@R_944_6889@
但是题目里还提出了一个进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
还是上面那句话c;要是双向链表就好了c;我们就双向比较。
所以c;考虑一下c;我们可以把链表的后半段翻转一下c;然后再比较。
为了完成这个目的c;大概需要分三步：
所以这种做法就是 876. 链表的中间结点@H_616_128@ 和 206. 反转链表@H_616_128@ 的组合。
代码实现如下：
/**
* 234. 回文链表
* 快慢指针法
*
* @param head
* @return
*/
public Boolean isPalindrome(ListNode head) {
//找到中间节点
ListNode midNode = findMid(head);
//翻转链表
ListNode tailHead = reverseList(@H_545_93@midNode);
//比较
while (tailHead != null) {
if (head.val != tailHead.val) {
return false;
}
head = head.next;
tailHead = tailHead.next;
}
return true;
}
/**
* 找到中间节点
*
* @param head
* @return
*/
ListNode findMid(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/**
* 翻转链表
*
* @param head
* @return
*/
ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode prev = null;
while (current != null) {
//保存下一个节点
ListNode temp = current.next;
//修改当前节点后继指向
current.next = prev;
//修改前趋节点
prev = current;
current = temp;
}
return prev;
}
@H_616_128@⏰ 时间复杂度：O(n)。
🏠 空间复杂度：O(1)。
ɡ5; 题目：141. 环形链表 (https://leetcode-cn.com/problems/linked-list-cycle/)
❓ 难度：简单
Ὅ5; 描述：
给定一个链表c;判断链表中是否有环。
如果链表中有某个节点c;可以通过连续跟踪 next 指针再次到达c;则链表中存在环。 为了表示给定链表中的环c;我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1c;则在该链表中没有环。注意：pos 不作为参数进行传递c;仅仅是为了标识链表的实际情况。
如果链表中存在环c;则返回 true 。 否则c;返回 false 。
💡 思路：
这道题是经典的快慢指针c;一个指针跑的块c;一个指针跑的慢c;如果链表成环的话c;慢指针一定会追上快指针。
@H_874_2913@
代码如下：
/**
* @return Boolean
* @Description: 141. 环形链表
* @author 三分恶
* @date 2021/7/25 20:16
*/
public Boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
//定义快慢指针
ListNode fast = head, slow = head;
//遍历链表
while (fast != null && fast.next != null) {
//快指针移动两步
fast = fast.next.next;
//慢指针移动一步
slow = slow.next;
//快、慢指针相遇
if (fast == slow) {
return true;
}
}
return false;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：142. 环形链表 II (https://leetcode-cn.com/problems/linked-list-cycle-ii/)
❓ 难度：中等
Ὅ5; 描述：
给定一个链表c;返回链表开始入环的第一个节点。 如果链表无环c;则返回 null。
为了表示给定链表中的环c;我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1c;则在该链表中没有环。注意c;pos 仅仅是用于标识环的情况c;并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
💡 思路：
这道题c;乍一看c;是 141. 环形链表@H_616_128@ 的进阶c;仔细一看c;没那么简单。
141. 环形链表@H_616_128@快指针只管追慢指针c;不管在哪追上就行c;但这个不行c;我们要返回追上的节点。
怎么办？
我们可以用一个集合把链表节点存进去c;要是成环的话c;放入的节点肯定会有重复的。
这个集合用什么呢？用HashSet比较合适。
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 142. 环形链表 II
* @author 三分恶
* @date 2021/7/25 20:40
*/
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
HashSet<ListNode> set = new HashSet<>(16);
while (head != null) {
//判断set中是否包含当前元素
if (set.contains(head)) {
return head;
}
//添加元素
set.add(head);
//继续迭代
head = head.next;
}
return null;
}
@H_616_128@⏰ 时间复杂度：O(n)。
🏠 空间复杂度：O(n)。
下图是一种比较典型的情况下c;做的推导[4]：
代码实现：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 142. 环形链表 II
* @author 三分恶
* @date 2021/7/25 20:52
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
//定义快、慢指针
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
//快慢指针相遇
if (fast == slow) {
//快指针重回head
fast = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
@H_616_128@⏰ 时间复杂度：O(n)。
🏠 空间复杂度：O(1)。
ɡ5; 题目：86. 分隔链表 (https://leetcode-cn.com/problems/partition-list/)
❓ 难度：中等
Ὅ5; 描述：
给你一个链表的头节点 head 和一个特定值 x c;请你对链表进行分隔c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
💡 思路：
可以创建两个链表c;一个链表存小节点c;一个链表存大节点c;最后再把两个链表合并起来。
代码如下：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 86. 分隔链表
* @author 三分恶
* @date 2021/7/25 21:58
*/
public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
}
//定义两个新链表
ListNode small = new ListNode(-1);
ListNode big = new ListNode(-1);
//小、大链表头节点
ListNode smallHad = small;
ListNode bigHead = big;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
//小链表插入节点
small.next = cur;
small = small.next;
} else {
//大链表插入节点
big.next = cur;
big = big.next;
}
cur = cur.next;
}
//防止成环
big.next = null;
//合并链表
small.next = bigHead.next;
return smallHad.next;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：328. 奇偶链表 (https://leetcode-cn.com/problems/odd-even-linked-list/)
❓ 难度：中等
Ὅ5; 描述：
给定一个单链表c;把所有的奇数节点和偶数节点分别排在一起。请注意c;这里的奇数节点和偶数节点指的是节点编号的奇偶性c;而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)c;时间复杂度应为 O(nodes)c;nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
@H_616_128@示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
@H_616_128@说明:
💡 思路：
和上道题类似c;我们也是将新建两个链表c;分别保存奇、偶数位的节点c;然后再把两个链表拼起来。
@H_85_3675@
代码如下：
/**
* @return 奇偶链表
* @Description:
* @author 三分恶
* @date 2021/7/25 22:18
*/
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
//奇数位链表
ListNode odd = new ListNode(-1);
//偶数位链表
ListNode even = new ListNode(-1);
//奇、偶链表头
ListNode oddHead = odd;
ListNode evenHead = even;
//计算位置
int index = 1;
//遍历
ListNode cur = head;
while (cur != null) {
// 奇
if (index % 2 == 1) {
odd.next = cur;
odd = odd.next;
} else {
//偶
even.next = cur;
even = even.next;
}
index++;
cur = cur.next;
}
//防止成环
even.next = null;
//合并链表
odd.next = evenHead.next;
return oddHead.next;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：剑指 Offer 25. 合并两个排序的链表(https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)
❓ 难度：简单
Ὅ5; 描述：
输入两个递增排序的链表c;合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
@H_616_128@本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/
💡 思路：
两个升序链表c;需要将其合并c;那么我们需要创建一个新链表c;遍历两个链表c;把小的那个接在后面。
代码如下：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 剑指 Offer 25. 合并两个排序的链表
* @author 三分恶
* @date 2021/7/25 22:36
*/
public ListNode @H_354_263@mergeTwoLists(ListNode l1, ListNode l2) {
//新链表
ListNode newNode = new ListNode(-1);
//新链表伪头
ListNode newHead = newNode;
while (l1 != null && l2 != null) {
//插入小的节点
if (l1.val <= l2.val) {
newNode.next = l1;
l1 = l1.next;
} else {
newNode.next = l2;
l2 = l2.next;
}
newNode = newNode.next;
}
//最后一个节点不要漏了
newNode.next = l1 != null ? l1 : l2;
return newHead.next;
}
@H_616_128@⏰ 时间复杂度：O(n)。
ɡ5; 题目：面试题 02.05. 链表求和 (https://leetcode-cn.com/problems/sum-lists-lcci/)
❓ 难度：中等
Ὅ5; 描述：
给定两个用链表表示的整数c;每个节点包含一个数位。
这些数位是反向存放的c;也就是个位排在链表首部。
编写函数对这两个整数求和c;并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)c;即617 + 295
输出：2 -> 1 -> 9c;即912
@H_616_128@**进阶：**思考一下c;假设这些数位是正向存放的c;又该如何解决呢?
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)c;即617 + 295
输出：9 -> 1 -> 2c;即912
@H_616_128@💡 思路：
这个就是我们上小学的时候很熟悉的四则运算。
两个链表从头c;也就是个位开始计算c;计算的结果c;需要进位c;我们用一个新链表来保存运算的结果。
如图：
代码实现如下：
/**
* @return cn.fighter3.linked_list.ListNode
* @Description: 面试题 02.05. 链表求和
* @author 三分恶
* @date 2021/7/26 2:40
*/
public ListNode addTwonumbers(ListNode l1, ListNode l2) {
//新链表
ListNode newNode = new ListNode(-1);
//新链表头
ListNode newHead = newNode;
//用来保存进制位
int carry = 0;
while (l1 != null || l2 != null) {
//判断当前位是否为空c;为空则设置为0
int l1Num = l1 == null ? 0 : l1.val;
int l2Num = l2 == null ? 0 : l2.val;
//求和
int sum = l1Num + l2Num + carry;
//更新进位
carry = sum / 10;
//求节点值
int nodeNum = sum % 10;
//添加节点
newNode.next = new ListNode(nodeNum);
//移动新链表指针
newNode = newNode.next;
//移动两个链表指针
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
//最后根据进位c;确定是否需要在尾部添加节点
if (carry != 0) {
newNode.next = new ListNode(carry);
}
return newHead.next;
}
@H_616_128@⏰ 时间复杂度：O(n)。
总结c;我随手写了个顺口溜。
简单的事情重复做c;重复的事情认真做c;认真的事情有创造性地做！
博主是一个算法萌新c;刷题路线和思路主要参考以下大佬！建议关注！
参考：
[1].https://github.com/youngyangyang04/leetcode-master
[2].https://github.com/chefyuan/algorithm-base
[3].https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/lang-man-ai-qing-gu-shi-zou-yi-zou-dui-f-35vn/
[4].https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/
以上是大佬教程为你收集整理的LeetCode通关：听说链表是门槛，这就抬脚跨门而入全部内容，希望文章能够帮你解决LeetCode通关：听说链表是门槛，这就抬脚跨门而入所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。