链表OJ题（一）

用户11820508

发布于 2026-01-12 14:56:02

题目一：移除链表元素

（1）题目链接

移除链表元素

（2）题目要求

（3）题解

操作：

cur代表当前需要删除的节点 prev代表当前需要删除节点cur的前驱节点
如果找到需要删除的节点，prev.next = cur.next;cur = cur.next;

如果没找到所要删除的节点，移动prev节点prev = cur;再移动cur判断下一个节点cur = cur.next;

最后的效果

如何处理头节点就是要删除的节点的情况？

先将头节点以外的删除再来考虑头节点位置即可 if(head.val == val) { head = head.next; }

也可先考虑头节点的情况，while循环判断

public void removeAllKey(int val) {
        //1. 判空
        if (head == null) {
            head = head.next;
        }
        //2. 定义prev 和 cur
        ListNode prev = head;
        ListNode cur = head.next;
        //3.开始判断并且删除
        while (cur != null) {
            if (cur.val == val) {
                //找到了
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        //4.处理头节点
        if(head.val == val) {
            head = head.next;
        }
    }

public ListNode removeElements(ListNode head, int val) {  
        // 1. 处理头节点  
        while (head != null && head.val == val) {  
            head = head.next;  
        }  
          
        // 2. 如果链表为空，直接返回  
        if (head == null) {  
            return head;  
        }  
          
        ListNode cur = head;  
        // 3. 开始判断并且删除  
        while (cur.next != null) {  
            if (cur.next.val == val) {  
                // 找到了  
                ListNode del = cur.next;  
                cur.next = del.next;  
            } else {  
                cur = cur.next;  
            }  
        }  
          
        // 4. 这里不需要再处理头节点，因为在循环开始前已经处理过了  
        return head;  
    }

题目二：反转链表

（1）题目链接

反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

（2）题目要求

（3）题解

思路：

采用头插法，将头节点以外的节点依次插入到头节点前面并改变next的指向

操作：

首先我们判断头节点head为空的情况，为空时返回head即可
cur节点表示什么？定义一个cur节点表示头结点的下一个节点，表示我们从头节点的下一个节点开始进行头插
curN节点表示什么？curN节点表示记录cur的下一个节点，当我们头插一个节点之后为了不丢失下一个结点的地址，我们需要提前记录下这个节点的地址，以便进行下一次头插
在进行一次头插后我们就改变头节点head的位置，同时cur向后移动进行下一次头插

public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }

题目三：链表的中间节点

（1）题目链接

链表的中间节点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

（2）题目要求

（3）题解

寻找中间节点用到了非常经典的快慢指针方法 思路：

使用两个指针变量，刚开始都位于链表的第 1 个结点，一个永远一次只走 1 步，一个永远一次只走 2 步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。
这道题换一种说法其实就是简单的数学问题，有两个人，fast和slow，fast的速度是2，slow的速度是1，它们从起点同时出发，当fast到达终点时，slow就在路程的中点，而slow所在的位置就是我们要返回的中间节点

操作：

fast和slow在同一起点，也就是head
循环条件是什么？ 这里我们要考虑到奇数节点和偶数节点的区别当链表的节点数为偶数时，fast == null时找到中间节点停止循环当链表的节点数为奇数时，fast.next == null时找到中间节点停止循环

public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            ListNode tmp = fast.next;
            fast = tmp.next;
            slow = slow.next;
        }
        return slow;
    }

题目四：返回倒数第k个节点

（1）题目链接

返回倒数第k个节点

https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

（2）题目要求

（3）题解

思路：因为题目要求是返回导数第k个节点，在这里我们依然使用的是快慢指针方法我们先让fast走k步，来抵消倒数的这个差值，然后再让fast和slow同时走

操作：

fast和slow从同一起点head出发
先将fast走k步再让它们同时走，直到fast为空时返回slow即可

    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
      for(int i = 0;i < k;i++) {
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

            return slow.val;
    }

题目五：合并两个有序链表

（1）题目链接

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

（2）题目要求

（3）题解

思路：

将两个链表的头节点依次进行比较，如果headA.val < headB.val，则tmp.next = headA，让headA往后走一步，tmp也往后走一步；headA.val > headB.val同理
如果A链表或B链表中有一个提前遍历完，那么再往后走就指null，这时tmp.next及时接上那个未遍历完的链表节点。

操作：

创建一个傀儡节点，用来指向两个链表头节点较小的一个
循环条件是什么？在两个链表的长度长度不同时，我们需要当一个链表判断完时接上另一个链表，这时我们要确保短的链表每个节点的val都判断到，也就是两个链表的不能为null，也就是headA != null && headB != null
要考虑两个链表空的情况，当A为空时直接指向B即可，否则相反

 public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newH = new ListNode();
        ListNode tmp = newH;
        while(headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            } else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if(headA != null) {
            tmp.next = headA;
        } else {
            tmp.next = headB;
        }
        return newH.next;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-26，如有侵权请联系 cloudcommunity@tencent.com 删除

变量