链表基础题

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记录第二节点，2
            ListNode 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时，直接返回head
            if (head == null || head.next == null) return head;
            // 用prev和post分别指向两个要交换的节点1和节点2
            ListNode prev = head, post = head.next;
            // p指针指向最近一次交换的结点2
            ListNode p = null;
            // 标记是否为首次交换
            boolean flag = true;
            while (prev != null && post != null) {
                // 交换prev和post在链表中的位置
                prev.next = post.next;
                post.next = prev;
                // 第一次交换时，需要更新head指向交换后得头节点（即原来的第二个节点）
                if (flag) {
                    // 更新head
                    head = post;
                    flag = false;
                }else {
                    // 如果不是第一次交换时，结点1和节点2左侧有已经交换过的节点，需要进行链接
                    p.next = post;
                }
                // p指针更新最近一次交换的结点2
                p = prev;
                prev = prev.next;
                // 如果prev指向的新的节点1为null，则结束循环；否则继续交换
                if (prev != null) {
                    post = prev.next;
                } else {
                    break;
                }
            }
            // 返回head
            return head;
        }
    }

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

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

踩坑点

代码如下：

    // 如果当前列表节点数量小于2，无需进行交换，直接返回
    if (head != null && head.next != null) {
        // node记录第二节点，2
        ListNode 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;
    }
}