算法题目总结-链表

1.环形链表

1.答案

package com.sunxiansheng.arithmetic.day11;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 141. 环形链表
 *
 * @Author sun
 * @Create 2025/1/16 10:36
 * @Version 1.0
 */
public class t141 {

    public boolean hasCycle(ListNode head) {
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 只要相遇了，就是有环
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

2.思路

快慢指针，只要相遇，就有环

2.两数相加

1.答案

package com.sunxiansheng.arithmetic.day11;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 2. 两数相加
 *
 * @Author sun
 * @Create 2025/1/16 10:39
 * @Version 1.0
 */
public class t2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 结果的头节点
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        // 进位
        int carry = 0;
        // 遍历两个链表的指针
        ListNode t1 = l1, t2 = l2;
        // 只要两个链表有一个不为空就进行遍历
        while (t1 != null || t2 != null) {
            // 获取两个节点的值
            int var1 = t1 == null ? 0 : t1.val;
            int var2 = t2 == null ? 0 : t2.val;
            // 求和
            int sum = var1 + var2 + carry;
            // 用完进位之后要恢复0
            carry = 0;
            // 判断是否要进位
            if (sum > 9) {
                carry = sum / 10;
                sum = sum % 10;
            }
            // 给结果赋值
            cur.next = new ListNode(sum);
            cur = cur.next;
            // 移动指针
            if (t1 != null) {
                t1 = t1.next;
            }
            if (t2 != null) {
                t2 = t2.next;
            }
        }
        // 检查是否还有没处理的进位
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return res.next;
    }
}

2.结果

核心是有一个进位的字段，多注意即可

3.反转链表

1.答案

package com.sunxiansheng.arithmetic.day12;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 206. 反转链表
 *
 * @Author sun
 * @Create 2025/1/17 09:56
 * @Version 1.0
 */
public class t206 {

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        // 哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // prev
        ListNode prev = dummy;
        // start
        ListNode start = head;
        // then
        ListNode then = start.next;
        while (start.next != null) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

2.思路

首先需要有prev、start、then，然后只要start.next不为空，就进行反转

4.反转链表 II

1.答案

package com.sunxiansheng.arithmetic.day12;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 92. 反转链表 II
 *
 * @Author sun
 * @Create 2025/1/17 09:52
 * @Version 1.0
 */
public class t92 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 找到prev、start、then
        // 哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 让cur指向left的前一个节点作为prev
        ListNode cur = dummy;
        for (int i = 0; i < left - 1; i++) {
            cur = cur.next;
        }
        ListNode prev = cur;
        ListNode start = cur.next;
        ListNode then = start.next;
        // 遍历次数
        int count = right - left;
        for (int i = 0; i < count; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

2.思路

找到prev、start、then，然后遍历次数为right - left

5.K 个一组翻转链表

1.答案

package com.sunxiansheng.arithmetic.day12;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 25. K 个一组翻转链表
 *
 * @Author sun
 * @Create 2025/1/17 10:21
 * @Version 1.0
 */
public class t25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        // 哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 提前记录prev
        ListNode prev = dummy;
        // 循环翻转
        while (true) {
            // 先判断有没有一组
            for (int i = 0; i < k; i++) {
                cur = cur.next;
                // 只要发现没有一组了，就返回结果
                if (cur == null) {
                    return dummy.next;
                }
            }
            // 到这里就说明有一组，可以翻转链表
            ListNode start = prev.next;
            ListNode then = start.next;
            reverseGroup(prev, start, then, k);
            // 更新prev
            prev = start;
            // 更新cur
            cur = prev;
        }
    }

    /**
     * 翻转一组链表
     *
     * @param prev
     * @param start
     * @param then
     * @param k
     */
    private void reverseGroup(ListNode prev, ListNode start, ListNode then, int k) {
        // 翻转次数
        int count = k - 1;
        for (int i = 0; i < count; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
    }
}

2.思路

就是先判断剩下的元素够不够k个，如果够就进行反转，翻转之后要更新prev和cur

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

1.答案

package com.sunxiansheng.arithmetic.day12;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 19. 删除链表的倒数第 N 个结点
 *
 * @Author sun
 * @Create 2025/1/17 10:44
 * @Version 1.0
 */
public class t19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 求出一共有多少个节点
        int count = 0;
        while (cur.next != null) {
            cur = cur.next;
            count++;
        }
        // 倒数第n个节点的前一个节点的索引
        int index = count - n;
        cur = dummy;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        // 目前cur指向了前一个节点，可以开始删除节点了
        cur.next = cur.next.next;
        return dummy.next;
    }
}

2.思路

就是先找到一共有多少个节点，再找到倒数第n个节点的前一个节点然后删除

7.删除排序链表中的重复元素 II

1.答案

package com.sunxiansheng.arithmetic.day13;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 82. 删除排序链表中的重复元素 II
 *
 * @Author sun
 * @Create 2025/1/19 09:32
 * @Version 1.0
 */
public class t82 {

    public static ListNode deleteDuplicates(ListNode head) {
        // 哨兵节点
        ListNode dummy = new ListNode(300);
        dummy.next = head;
        ListNode cur = dummy;
        // 记录前一个位置
        ListNode pre = dummy;
        while (cur.next != null) {
            cur = cur.next;
            if (cur.next == null || cur.val != cur.next.val) {
                pre = cur;
            } else {
                // 到这就说明pre的后两个元素相同
                // 记录一下值
                int val = cur.val;
                while (cur.next != null && val == cur.next.val) {
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = pre;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(3);
        deleteDuplicates(head);
    }
}

2.思路

就是有一个pre来记录前一个位置，每次循环都让cur先走一步，然后判断当前元素跟下一个元素是不是相同，如果不相同或者目前是最后一个元素，就让pre也指向cur，如果说当前元素跟下一个元素是相同的，那么就删除相同元素，最终让cur指向pre

8.旋转链表

1.答案

package com.sunxiansheng.arithmetic.day13;

import com.sunxiansheng.arithmetic.util.ListNode;

import java.util.List;

/**
 * Description: 61. 旋转链表
 *
 * @Author sun
 * @Create 2025/1/19 10:29
 * @Version 1.0
 */
public class t61 {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        // 哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 计算链表总长度
        int length = 0;
        while (cur.next != null) {
            cur = cur.next;
            length++;
        }
        // 如果余数为0，则直接返回
        if (k % length == 0) {
            return head;
        }
        // 记录链表末尾元素
        ListNode end = cur;
        // 移动到正数第length - k % length个位置
        int index = length - k % length;
        cur = dummy;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        dummy.next = cur.next;
        // 切断，否则会有环
        cur.next = null;
        end.next = head;
        return dummy.next;
    }
}

2.思路

首先计算链表的总长度，然后记录链表末尾元素，再通过计算，找到正数第length - k % length个位置，然后根据题意进行组装，不过要注意切断一下，否则会有环

9.LRU 缓存

1.答案

package com.sunxiansheng.arithmetic.day13;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 146. LRU 缓存
 *
 * @Author sun
 * @Create 2025/1/19 10:55
 * @Version 1.0
 */
public class LRUCache {

    // 双向链表的节点
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {}

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 双向链表的头尾指针
    DLinkedNode head, tail;
    // map：key是key，value是双向链表的节点
    private Map<Integer, DLinkedNode> map;
    // 容量
    private int capacity;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        // 头结点和尾节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    // 获取元素
    public int get(int key) {
        // 从map中去获取key
        DLinkedNode dLinkedNode = map.get(key);
        if (dLinkedNode == null) {
            return -1;
        }
        // 获取之后，将元素放到链表头部
        moveToHead(dLinkedNode);
        return dLinkedNode.value;
    }

    private void moveToHead(DLinkedNode dLinkedNode) {
        // 首先需要在链表中删除这个元素
        delete(dLinkedNode);
        // 然后将元素插入到头部
        insertToHead(dLinkedNode);
    }

    private void insertToHead(DLinkedNode dLinkedNode) {
        dLinkedNode.next = head.next;
        dLinkedNode.prev = head;
        head.next.prev = dLinkedNode;
        head.next = dLinkedNode;
    }

    private static void delete(DLinkedNode dLinkedNode) {
        dLinkedNode.prev.next = dLinkedNode.next;
        dLinkedNode.next.prev = dLinkedNode.prev;
    }

    // 插入或更新元素
    public void put(int key, int value) {
        // 先获取元素
        DLinkedNode dLinkedNode = map.get(key);
        // 如果元素有值了，就替换值，并移动到头部
        if (dLinkedNode != null) {
            dLinkedNode.value = value;
            moveToHead(dLinkedNode);
        } else {
            // 没有值则需要新增元素
            dLinkedNode = new DLinkedNode(key, value);
            // 确保容量足够
            ensureCapacity(map.size() + 1);
            // 目前容量一定足够，直接插入到头部即可
            map.put(key, dLinkedNode);
            insertToHead(dLinkedNode);
        }
    }

    private void ensureCapacity(int newSize) {
        if (newSize <= capacity) {
            return;
        }
        // 如果容量不够，则需要删除最后的一个元素
        map.remove(tail.prev.key);
        delete(tail.prev);
    }
}

2.思路

使用双向链表+map来做

首先需要一个双向链表的类，key，value，next，prev即为属性

然后需要三个参数，双向链表的前后指针，map，容量

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

1.答案

package com.sunxiansheng.arithmetic.day13;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 24. 两两交换链表中的节点
 *
 * @Author sun
 * @Create 2025/1/19 12:01
 * @Version 1.0
 */
public class t24 {

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 提前记录prev
        ListNode prev = dummy;
        // 循环翻转
        while (true) {
            // 先判断是否有一组
            for (int i = 0; i < 2; i++) {
                if (cur.next == null) {
                    return dummy.next;
                }
                cur = cur.next;
            }
            // 到这里就是有一组了，开始翻转
            ListNode start = prev.next;
            ListNode then = start.next;
            reverse(prev, start, then);
            // 更新prev和cur
            prev = start;
            cur = prev;
        }
    }

    // 两个一组翻转链表
    private void reverse(ListNode prev, ListNode start, ListNode then) {
        start.next = then.next;
        then.next = prev.next;
        prev.next = then;
        then = start.next;
    }
}

2.思路

就是两个一组翻转链表，翻转链表的次数是节点数减一，然后要提前记录prev，并且在翻转后更新prev和start

11.环形链表 II

1.答案

package com.sunxiansheng.arithmetic.day13;

import com.sunxiansheng.arithmetic.util.ListNode;

/**
 * Description: 142. 环形链表 II
 *
 * @Author sun
 * @Create 2025/1/19 12:31
 * @Version 1.0
 */
public class t142 {

    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 (slow == fast) {
                // 这样只能代表有环，如果想要找到入环的第一个节点，就要让slow等于head，然后一起移动
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

2.思路

发现有环之后，如果想要找到入环的第一个节点，就要让slow等于head，然后一起移动，直到相遇