链表OJ题（二）

用户11820508

发布于 2026-01-12 14:57:09

题目一：链表分割

题目链接

链表分割

题目要求

题解

将链表分为两个区域，大于x的和小于x的，前半部分用bs,be表示，后半部分用as,ae表示，最后将be和as拼接即可

bs,be,as,ae如何赋值？我们将bs,be,as,ae先置为空，因为我们不知道第一个节点相对于x的大小，所以我们需要使用分支语句来进行判断，大于就把cur赋值给as, ae => bs = be = cur; 小于就把cur赋值给bs, be; => as = ae = cur;
不同大小情况下的val如何处理？ 每一个节点的大小都是未知的，所以我们需要将链表遍历来进行依次判断，也就是 cur = cur.next; 遍历过程中：当cur.val小于x时，be.next = cur; be = be.next; 当cur.val大于x时，ae.next = cur;ae = ae.next;
我们需要在判断完第一个节点val与x的大小情况并赋值后，紧接着判断后面的节点，所以这里要用到两个if else语句
可能会出现都大于x或都小于x的情况，当都大于x时返回as节点即可，否则返回bs
预防最后一个节点的next值不为空

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null) {
                    as = ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //可能会出现都大于x或都小于x的情况，当都大于x时返回as节点即可，否则返回bs
        if(bs == null) {
            return as;
        }
        //拼接
        be.next = as;
        //预防最后一个节点的next值不为空
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
}

题目二：链表的回文结构

题目链接

链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

题目要求

题解

我们需要实现的效果是：

第一步先找到中间节点，slow就是中间节点
怎样？如何？进行反转 cur表示slow的下一个节点，实现cur的next反转为slow； curN表示cur的下一个节点，防止cur反转后下一个节点的丢失；将中间节点后面的节点进行反转，定义cur来表示slow的下一个节点，方便将cur的next改为slow，因为slow后面需要反转的节点可能不止一个，我们定义curN记录cur的下一个节点防止丢失，记录下后将cur进行反转，即cur.next = slow，紧接着slow和cur往后走并循环这一操作直到走过整个链表，即cur != null
判断回文，head从前往后走，slow从后往前走，直到相遇
链表结点个数为偶数个时怎么处理？ 偶数个节点，head.next == slow时表明是回文结构

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //找出链表的中间节点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //链表的反转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;//记录cur的下一个节点防止丢失
            //开始反转
            cur.next = slow;
            //slow和cur往后走
            slow = cur;
            cur = curN;
        }
        //判断回文，head从前往后走，slow从后往前走，直到相遇
        while(head != slow) {
            if(head.val != slow.val){
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
            
        }
        return true;
        
    }
}

题目三：删除有序链表重复元素-I

题目链接

删除有序链表中重复的元素-I

https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=196&tqId=37064&ru=/exam/oj

题目要求

只留下重复元素的一个

题解

如果头节点为空直接返回head即可
因为链表是有序的，这说明重复的元素都是相邻的，所以我们只需要将cur.val与cur.next的val进行比较即可，但由于重复元素可能大于两个，所以cur.val是一直往后移动的

因为是判断当前一位与下一位是否相等，所以要保证这两个都不能为空，也就是cur != null && cur.next != null
如果当前一位与下一位相等则进行删除，继续判断下一位，否则cur正常遍历
直到cur判断完最后一个元素后停止循环。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //遍历指针
        ListNode cur = head;
        //指针当前和下一位不为空
        while (cur != null && cur.next != null) {
            //如果当前与下一位相等则忽略下一位
            if (cur.val == cur.next.val)
                cur.next = cur.next.next;
            //否则指针正常遍历
            else
                cur = cur.next;
        }
        return head;

    }
}

题目四：删除有序链表中重复元素-II

题目链接

删除有序链表中重复的元素-II

https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=196&tqId=37063&ru=/exam/oj

题目要求

将重复元素全部删除

题解

一样的思路，通过判断cur.val 和 cur.next.val是否相等
写一个循环用来遍历整个链表，当cur.val 和 cur.next.val相等时我们就跳过这个节点，而此时肯会存在两个以上的相等，所以需要再写一个循环来判断；如果不相等则将该节点添加到新链表当中

操作：

创建一个傀儡节点，判断过程中不是重复的节点时就追加到该节点的后面并初始化一个临时指针tmp指向newHead，以便后续的拼接
使用while循环遍历原始链表。如果当前节点cur的下一个节点存在且两者值相等，则进入内层while循环，跳过所有与cur值相同的节点，直到找到不重复的元素。如果当前节点cur的下一个节点不存在或两者值不相等，则将cur添加到新链表中

在while循环结束后，将tmp.next设为null。
返回新链表的头节点newHead.next。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        ListNode cur = head;
        ListNode newHead = new ListNode(-1); // 创建一个虚拟节点
        ListNode tmp = newHead;//用来连接

        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                // 跳过所有重复节点
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
            } else {
                // 将非重复节点添加到新链表中
                tmp.next = cur;
                tmp = tmp.next; // 移动tmp到新的节点
            }
            // 移动cur到下一个节点
            cur = cur.next;
        }

        // 确保新链表的最后一个节点的next为null
        tmp.next = null;

        return newHead.next;
    }
}

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

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

null