链表基础题

206. 反转链表

问题描述

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路与代码实现

/*** 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 reverseList(ListNode head) {if(head == null){	// 空链表直接返回return null;}ListNode s = head;ListNode pre = null, post;// pre指向新的链表头结点，s指向当前链表的头结点，post指向s所指结点的下一个结点while(s!=null){// 逐个把当前节点挂在新链表post = s.next; s.next = pre;pre = s;   s = post;}return pre;}
}

时间复杂度：O(n)

空间复杂度：O(1)

踩坑点

无

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

问题描述

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

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

解题思路与代码实现

 /*** 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 {/*** 递归解法：* 返回值：交换完成的子链表* 调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换* 终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换*/// 以1->2->3->4为例public ListNode swapPairs(ListNode head) {// 如果当前列表节点数量小于2，无需进行交换，直接返回if (head != null && head.next != null) {// node记录第二节点，2ListNode node = head.next;head.next = swapPairs(node.next);   // 第一节点指向剩余待交换链表头结点，先执行这行，避免形成环node.next = head;   // 如果先执行这行，会导致1->2->3变成1->2->1，形成环结构造成栈溢出return node;}return head;}/*** 解题思路：* 每次用prev和post分别指向两个要交换的节点1和节点2，p指针指向上一次交换的结点2* 第一次交换时，需要更新head指向交换后得头节点（即原来的第二个节点）* 如果不是第一次交换时，结点1和节点2左侧有已经交换过的节点，需要将二者链接起来* 注意，在第一次交换时，需要更新head*/public ListNode swapPairs(ListNode head) {// 节点数少于2时，直接返回headif (head == null || head.next == null) return head;// 用prev和post分别指向两个要交换的节点1和节点2ListNode prev = head, post = head.next;// p指针指向最近一次交换的结点2ListNode p = null;// 标记是否为首次交换boolean flag = true;while (prev != null && post != null) {// 交换prev和post在链表中的位置prev.next = post.next;post.next = prev;// 第一次交换时，需要更新head指向交换后得头节点（即原来的第二个节点）if (flag) {// 更新headhead = post;flag = false;}else {// 如果不是第一次交换时，结点1和节点2左侧有已经交换过的节点，需要进行链接p.next = post;}// p指针更新最近一次交换的结点2p = prev;prev = prev.next;// 如果prev指向的新的节点1为null，则结束循环；否则继续交换if (prev != null) {post = prev.next;} else {break;}}// 返回headreturn head;}}

递归解法时间复杂度：O(n)

递归解法空间复杂度：O(1)

踩坑点

代码如下：

    // 如果当前列表节点数量小于2，无需进行交换，直接返回if (head != null && head.next != null) {// node记录第二节点，2ListNode node = head.next;head.next = swapPairs(node.next);   // 第一节点指向剩余待交换链表头结点，先执行这行，避免形成环node.next = head;   // 如果先执行这行，会导致1->2->3变成1->2->1，形成环结构造成栈溢出return node;}

如果先执行node.next = head，会形成环，造成栈溢出。

141. 环形链表

问题描述

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

解题思路与代码实现

解题思路：

使用快慢指针，fast指针每次走两步，slow指针每次走一步；
如果有环，fast会重新追上slow；
如果无环，则fast会为null；

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null){  // 节点数量小于等于1，不可能有环return false;}boolean flag = false;// 快慢指针ListNode slow = head ,fast = head; while(fast!=null && slow!=null){slow = slow.next;   // slow走一步fast = fast.next;    // fast走两步if(fast!=null && fast.next != null){fast = fast.next;}else{  // 无环break;   }if(fast == slow){   // 二者指向同一节点flag = true;break;}}return flag;}
}

踩坑点

无

142. 环形链表 II

问题描述

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

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

不允许修改 链表。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

解题思路与代码实现

解题思路：

先判断是否有环，使用快慢指针，fast指针每次走两步，slow指针每次走一步；
如果有环，fast移到head头结点，然后fast和slow每次都走一步，相遇时返回相遇节点；
如果无环，则返回null，

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){  // 节点数量小于等于1，不可能有环return null;}// 快慢指针判断是否有环ListNode slow = head ,fast = head; while(fast!=null && slow!=null){slow = slow.next;   // slow走一步fast = fast.next;    // fast走两步if(fast!=null && fast.next != null){fast = fast.next;}else{  // fast 指针走过链表末端，说明链表无环，return null; }if(fast == slow){   // 二者指向同一节点fast = head;break;}}//有环while (fast != null){if (fast == slow ){return fast;}fast = fast.next;slow = slow.next;}return null;}
}

踩坑点

无

19. 删除链表的倒数第 N 个结点

问题描述

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

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

解题思路与代码实现

先设置指针q提前走n步；
指针s从头结点开始，和q一样每次移动一步，这个过程中用p记录s的前一个节点（用于删除中间节点），直到q为null停止；

此时s指向了待删除的节点
判断p是否为null

p==null：需要删除头结点；

p!=null：需要删除中间节点；

/*** 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 removeNthFromEnd(ListNode head, int n) {    // n<= head.length// 安排一个指针，先走n步int count = 0;ListNode q = head, s = head, p = null;while (q != null && count < n) {count++;q = q.next;}// s,q同时移动，当q为null时，s为需要删除的节点while (q != null) {p = s;  // 记录s的前一个结点，方便删除s = s.next;q = q.next;}if (p != null) {  // 说明当前删除的是头结点p.next = s.next;// 删除s指向的节点s.next = null;}else{ // 说明当前是删除头结点head = head.next;}return head;}
}