---
title: "【面试算法笔记】0203-链表-链表其他操作"
source: https://www.zbhgis.com/note/note-20260510-1
author: zbhgis 浩瀚地学
created: 2026-05-10
tags: [面试算法笔记, 算法, LeetCode]
---

> 本文来自浩瀚地学，规范页面（含代码高亮与图片灯箱）：https://www.zbhgis.com/note/note-20260510-1
# 【面试算法笔记】0203-链表-链表其他操作

个人主页：https://github.com/zbhgis

# 前言

本系列主要记录自己学习算法的过程中的感悟。

# 力扣24. 两两交换链表中的节点

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

## 注意点

1.

node0   node1  node2  node3

dummy    1         2         3         4         5

两两交换的话，先判断一下node0和node1的next是不是null，就是判断是否还有可以交换的节点。

有的话，就node0指向node2，node2指向node1，node1指向node3，这样子就变成了

node0   node2  node1  node3

dummy    2         1         3         4         5

2.

然后需要开启下一轮遍历的话，更新node0为node1，更新node1为node3。

node2和node3会自动更新

​                      node0   node1  node2  node3

dummy    2         1         3         4         5

3.

最后遍历结束，返回头节点。

## 代码

```Java
/**
 * 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 swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode node0 = dummy;
        ListNode node1 = head;

        while(node0.next != null && node1.next != null) {
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;
            node0.next = node2;
            node2.next = node1;
            node1.next = node3;

            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}
```

## 时空复杂度分析

单层循环，需要遍历n/2次，因此时间复杂度为O(n)

空间复杂度为O(1)

# 力扣19. 删除链表的倒数第N个节点

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

## 注意点

双指针做法。

快指针先走n个节点，然后快慢指针再一起开始扫描，这样子当快指针到尾节点的时候时候，慢指针的下一个节点就是目标节点。

## 代码

```Java
/**
 * 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) {
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n -- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}
```

## 时空复杂度分析

加起来一共遍历了n次，n为链表长度，因此时间复杂度为O(n)

空间复杂度为O(1)

# 力扣160. 相交链表

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

## 注意点

就是需要让两个链表走共同的路程，之后保证停留在相同节点（如果本来就无法相遇，那么就是都停留在空节点上）

## 代码

```Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }
}
```

## 时空复杂度分析

单层循环，需要遍历m+n次，m+n为两个链表长度之和，因此时间复杂度为O(m+n)

空间复杂度为O(1)

# 力扣142. 环形链表 II

链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

## 注意点

设头节点到入环口需要走a步。设环长为c。设相遇的时候，慢指针走了b步，那么快指针走了2b步。

设快指针比慢指针多走了k圈，即2b－b=kc，得b=kc。

慢指针从入环口开始，在环中走了b－α=kc－α步到达相遇点。

这说明从相遇点开始，再走a步，就恰好走到入环口了！

虽然不知道a是多少，但如果让头节点和慢指针同时走，恰好a步后二者必定相遇，且相遇点就在入环口

## 代码

```Java
/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }
                return head;
            }
        }
        return null;
    }
}
```

## 时空复杂度分析

双层循环，但是外层循环只进行1次，内层循环也进行1次，且两层循环每次最多n的常数倍数，因此时间复杂度为O(n)

空间复杂度为O(1)

# 参考

https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html