当前位置： 首页 > article >正文

【算法通关村 Day2】反转链表

article 2025/2/21 18:28:19

链表反转青铜挑战

手写链表反转

方式一 头插法

  • 借助虚拟头节点：dummyHead 是一个值为 0 的节点，它的 next 一开始指向 null。我们不关心 dummyHead 的值，只关注它的 next 指针，它将最终指向反转后的链表头部。
  • 保存当前节点的下一个节点
  • 将当前节点插入到虚拟头节点后面
  • 更新虚拟头节点的 next 为当前节点
  • 继续遍历链表

public class ReverseList {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public ListNode reverseList(ListNode head){
        ListNode dummyHead = new ListNode(0);
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;
            current.next = dummyHead.next;
            dummyHead.next = current;
            current = nextNode;
        }

        return dummyHead.next;
    }    
}

方式二 迭代法（使用 3 个指针）

  • next = curr.next：保存当前节点的 next，这样我们在修改 curr.next 时，不会丢失对下一个节点的引用。
  • curr.next = prev：将当前节点的 next 指向前一个节点 prev，这样就完成了当前节点的反转。
  • prev = curr：将 prev 更新为当前节点，为下一次反转做准备。
  • curr = next：将 curr 移动到下一个节点，继续进行反转。
  • prev 最终是新的头节点
public class ReverseList {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;

        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }    
}

迭代法通过三个指针来逐步反转链表，时间复杂度为 O(n)，空间复杂度为 O(1)，只用了常数的额外空间。

方式三 递归法

  • 递归终止条件：如果链表为空（head == null）或者只有一个节点（head.next == null），递归就结束，直接返回当前节点 head，作为新链表的头。

  • 递归过程：

    • 在 head.next != null 时，递归调用 reverseList(head.next) 来反转当前节点后面的链表部分，直到递归到链表的最后一个节点。
    • 递归返回时，会把当前节点的 next 指针指向前一个节点，逐步完成链表的反转。

  • 递归的回溯阶段：

    • 当递归返回时，head 的 next 指针需要指向前一个节点（head.next.next = head），然后将 head.next 设置为 null，断开原来链表的连接，防止链表形成环。
    • 这种逐步“反转”指针的过程，实际是从链表尾部逐渐完成反转，最终形成完全反转的链表。

  • 返回新链表头：递归的返回值 newHead 始终指向反转后的链表头部，最终返回 newHead 作为反转后的链表头。

public class ReverseList {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode newHead = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

时间复杂度是 O(n)，空间复杂度是 O(n)。每一次递归都需要占用栈空间，递归深度为链表长度，最坏情况下空间复杂度为 O(n)。

链表反转白银挑战

指定区间反转

已知链表头节点和整数left和right，left<right<链表长度，要求反转链表从位置left到位置right的链表节点，返回反转后的链表。leetcode

  • 虚拟头节点：我们使用虚拟头节点（dummy）来简化头节点的处理，避免特殊情况处理，比如链表从头开始反转。
  • 定位 prev 节点：我们将 prev 移动到 left-1 的位置。
  • 反转部分链表：使用 for 循环反转从 left 到 right 的部分。在每次循环中：
    • next 存储当前节点的下一个节点；
    • 将当前节点的 next 指向 next.next，使当前节点与后面的节点脱离；
    • 将 next 插入到 prev 后面，完成反转。
public class ReverseBetween {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public static ListNode reverseBetween(ListNode head, int left, int right){
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        for(int i = 0; i < left-1; i++){
            prev = prev.next;
        }

        ListNode curr = prev.next;
        ListNode post = null;
        for(int i = 0; i < right - left; i++){
            post = curr.next;
            curr.next = post.next;
            post.next = prev.next;
            prev.next = post;
        }
        return dummyHead.next;
    }
}
  • 这个算法的时间复杂度是 O(n)，其中 n 是链表的长度，因为我们只需要遍历链表一次。

两两交换链表节点

已知一个链表，要求两两交换链表中的节点，返回交换后的头节点(智能交换节点，不能只交换节点值)。详见leetcode

  • dummyHead 节点：为了简化边界处理（特别是当链表长度为 0 或 1 时），我们创建了一个虚拟节点 dummyHead，它的 next 指针指向链表的头节点。dummyHead节点本身不会参与交换，但它帮助我们处理边界情况。

  • current 指针：current 是指向当前交换对的前一个节点，它初始化为 dummyHead。每次交换后，current 更新为交换后的第一个节点。

  • 交换操作：

    • 每次迭代我们交换 head 和 head.next 这两个节点。
    • current .next 指向交换后的第二个节点（即 head.next）。
    • first.next 指向交换后第二个节点的下一个节点（即 head.next.next）。
    • second.next 指向第一个节点（即 head）。

  • 更新指针：

    • 在交换完当前一对节点后，更新 current 指向 first（即交换后的第一个节点）。
    • 然后将 head 更新为 first.next，继续处理下一对节点。

  • 返回结果：最终返回 dummyHead.next，这是交换后的新头节点。

public class SwapPairs {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public static ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);

        ListNode current = dummyHead;

        dummyHead.next = head;

        while (head != null && head.next != null) {
            ListNode first = head;
            ListNode second = head.next;

            current.next = second;
            first.next = second.next;
            second.next = first;

            current = first;
            head = first.next;
        }

        return dummyHead.next;
    }
}

时间复杂度是 O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。

空间复杂度是 O(1)，我们只使用了常数级别的额外空间。

单链表加一

已知一个单链表，用这个单链表来表示一个整数，从表头到表尾表示从高位到低位，要求将这个数加1后返回。

运算过程中会出现：无进位，有进位但不在首位，有进位且在首位 这三种情况。

首先反转链表，然后像加法运算一样从链表的头部开始进行加 1 操作，最后再将链表反转回去。这样做的优点是避免了使用栈，同时实现相对简单。

步骤：

  1. 反转链表：先反转链表，这样可以从个位开始进行加法操作。
  2. 加法操作：从链表的头部开始加 1，处理进位。
  3. 反转链表回去：最后，反转链表以恢复原来的顺序。
public class PlusOne {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode plusOne(ListNode head) {
        if (head == null) return new ListNode(1);

        // 1. 反转链表
        ListNode reversedHead = reverseList(head);
        
        // 2. 从反转后的链表开始加 1
        ListNode current = reversedHead;
        int carry = 1; // 初始加1
        while (current != null && carry > 0) {
            int sum = current.val + carry;
            current.val = sum % 10;  // 更新当前节点值
            carry = sum / 10;  // 计算进位
            current = current.next;
        }

        // 如果最后仍然有进位
        if (carry > 0) {
            ListNode newNode = new ListNode(carry);
            current.next = newNode;
        }

        // 3. 反转链表回去
        return reverseList(reversedHead);
    }

    // 反转链表的辅助函数
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}
  • 反转链表的时间复杂度是 O(n)，其中 n 是链表的长度。
  • 遍历链表进行加法操作的时间复杂度是 O(n)。
  • 最终反转链表的时间复杂度是 O(n)。

除了使用反转链表也可以使用栈。因为栈是后进先出（LIFO）结构，所以链表的最后一个节点会被最先取出来，这样我们就能从个位开始进行加法运算。

  • add 初始为 1，因为我们需要给链表表示的数字加 1。
  • flag 用于表示进位（1 代表有进位，0 代表没有进位）。
  • sum 是当前节点的值、加 1 的值以及进位的值之和。

处理进位：

  • 如果 sum 大于等于 10，说明需要进位。我们把当前节点的值更新为 sum - 10，并设置 flag = 1 表示有进位。
  • 如果 sum 小于 10，则直接更新当前节点的值，并把 flag 设置为 0 表示没有进位。
  • 一旦完成加法，add 会被设置为 0，因为我们只需要给链表的最后一位加 1。
  • 如果最后一个节点加法后仍然有进位（即 flag == 1），说明大整数本身发生了进位（比如 999 + 1 变成了 1000）。此时，我们需要在链表的头部添加一个新的节点 1。
import java.util.Stack;

public class PlusOne {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public static ListNode plusOne(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;

        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        int add = 1;

        int flag = 0;

        boolean carry = true;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            int sum = node.val + add + flag;

            if (sum >= 10) {
                node.val = sum - 10;
                flag = 1;
            } else {
                node.val = sum;
                flag = 0;
            }
            add = 0;
        }

        if (flag == 1) {
            ListNode newHead = new ListNode(1);
            newHead.next = head;
            head = newHead;
        }

        return head;
    }
}

链表加法

两个非空链表存储两个整数，数字最高位位于链表开始位置，每一个节点存储一个数字，将这两个链表的数字相加，返回一个新的链表。(假设除了数字0以外，这两个数字不会以0开头)。

反转链表：由于链表的存储顺序是从高位到低位，直接从链表头开始加法比较麻烦。我们可以首先将两个链表反转，这样可以从低位开始逐位加法。

  • 我们初始化了 carry = 0，表示初始没有进位。
  • 然后进入 while 循环，直到两个链表都遍历完并且没有进位为止。
  • 每次循环时，我们从两个链表（如果有节点的话）中取出当前位的值，并加上进位 carry。
  • 然后，我们计算当前位的值（digit = sum % 10）和进位（carry = sum / 10）。
  • 将计算得到的 digit 存入一个新的链表。
  • 加法完成后，resultHead 中存储的链表是反转的，所以最后我们需要再将其反转一次，得到最终的结果链表。
public class AddTwoNumbers {
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val){
            this.val = val;
        }    
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode reversedL1 = reverseList(l1);
        ListNode reversedL2 = reverseList(l2);

        ListNode resultHead = null;
        ListNode current = null;
        int carry = 0;

        while (reversedL1 != null || reversedL2 != null || carry != 0) {
            int sum = carry;
            if (reversedL1 != null) {
                sum += reversedL1.val;
                reversedL1 = reversedL1.next;
            }
            if (reversedL2 != null) {
                sum += reversedL2.val;
                reversedL2 = reversedL2.next;
            }

            carry = sum / 10;
            int digit = sum % 10;

            ListNode newNode = new ListNode(digit);

            if (resultHead == null) {
                resultHead = newNode;
                current = resultHead;
            } else {
                current.next = newNode;
                current = current.next;
            }
        }

        return reverseList(resultHead);
    }    
    private ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}

时间复杂度：

  • 反转两个链表的时间复杂度是 O(n) 和 O(m)，其中 n 和 m 分别是两个链表的长度。
  • 遍历两个链表并进行加法操作的时间复杂度是 O(max(n, m))。
  • 反转结果链表的时间复杂度是 O(max(n, m))。

因此，总的时间复杂度是 O(max(n, m))。

空间复杂度：

由于反转链表和创建新链表的操作，我们需要 O(max(n, m)) 的空间来存储结果链表。

链表反转黄金挑战

K个一组反转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

  • 虚拟头节点：创建一个虚拟头节点 dummy，让它指向原链表的头节点。这样可以简化操作，尤其是在翻转链表时不需要考虑头节点的特殊情况。
  • 长度计算：遍历链表一次，计算链表的长度 length。然后，在每次翻转时，判断剩余的节点是否有足够的数量（至少为 k 个）来进行翻转。
  • 翻转过程：
    • 每次翻转前，curr 指向当前需要翻转的一组的第一个节点，next 指向下一个节点。
    • 通过修改指针实现翻转，每次将 next 节点插入到当前组的最前面。
    • 翻转一组后，更新 prev 为当前组的尾节点，准备翻转下一组。
  • 更新链表结构：翻转完成后，返回 dummy.next，即新的链表头。
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 如果链表为空或k为1，不需要翻转
        if (head == null || k == 1) {
            return head;
        }

        // 虚拟头节点，简化处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 用prev指针指向翻转的前一个节点
        ListNode prev = dummy;
        ListNode curr = head;
        ListNode next = null;
        
        // 计算链表的长度
        int length = 0;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // 每k个节点一组进行翻转
        while (length >= k) {
            curr = prev.next;  // 当前组的第一个节点
            next = curr.next;  // 当前节点的下一个节点
            
            // 进行翻转操作
            for (int i = 1; i < k; i++) {
                curr.next = next.next;  // 将当前节点的next指向next.next，断开原有连接
                next.next = prev.next;  // 将next的next指向prev.next，这样可以将next节点放到最前面
                prev.next = next;       // prev的next指向next，使链表连接起来
                next = curr.next;       // 更新next节点
            }
            
            prev = curr;   // prev指向当前组翻转后的尾节点
            length -= k;   // 更新剩余的节点数
        }

        return dummy.next;
    }
}
  • 时间复杂度：O(n)，其中 n 是链表的长度。每个节点最多被遍历两次（一次计算长度，一次进行翻转）。
  • 空间复杂度：O(1)，我们只使用了常数级的额外空间。

http://www.kler.cn/a/552821.html

相关文章：

  • 【网络编程】网络编程基础：TCP/UDP 协议
  • 学习数据结构（10）栈和队列下+二叉树（堆）上
  • 计算机视觉：神经网络实战之手势识别(附代码)
  • Alluxio Enterprise AI 3.5 发布，全面提升AI模型训练性能
  • Docker 多阶段构建：优化镜像大小
  • C#_子窗体嵌入父窗体
  • YOLOv11-ultralytics-8.3.67部分代码阅读笔记-annotator.py
  • 【第3章：卷积神经网络（CNN）——3.7 数据增强与正则化技术】
  • go 树形结构转为数组
  • win11 labelme 汉化菜单
  • matlab质子磁力仪传感器线圈参数绘图
  • 确保设备始终处于最佳运行状态，延长设备的使用寿命，保障系统的稳定运行的智慧地产开源了
  • Effective C++读书笔记——item52（如果编写了 placement new，就要编写 placement delete）
  • Spring Security，servlet filter，和白名单之间的关系
  • 【前端ES】ECMAScript 2023 (ES14) 引入了多个新特性，简单介绍几个不为人知但却好用的方法
  • 【Python爬虫(14)】解锁Selenium：Python爬虫的得力助手
  • npm、yarn、pnpm 的异同及为何推荐 pnpm
  • DeepSeek AI 完全使用指南：从入门到精通
  • Node.js 版本与 npm 的关系及版本特性解析：从开源项目看演进
  • 腿足机器人之九- SLAM基础