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

leetcode 面试题 02.04. 分割链表

article 2024/9/24 13:16:45

原题为：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于x 的节点之前。
你不需要保留每个分区中各节点的初始相对位置。

测试示例如下：
在这里插入图片描述

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

思路：没有在原链表上进行修改，而是新建一个链表ans，用指针p1指向链表ans的头节点。然后遍历输入的链表head，如果head中某个节点值val小于x，那么将这个节点连接在p1指针后面(并修改p指针的指向)；否则，这里分为两种情况，初始化指针p2，如果p2为NULL，那么直接把当前节点连接在p1指针后面，并将p2指向当前新连入的节点；否则把当前节点连接在p2指针后面，并修改p2指针的指向。最后这个遍历完成之后，返回ans的下一个节点即可。

把上述示例用我自己的思路描述如下：

在这里插入图片描述
参考代码如下(Python):

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
        
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """

        if not head or not head.next:
            return head

        p = head
        ans = ListNode(0)
        p1 = ans
        p2 = None
        while p:
            next = p.next
            p.next = None
            if p.val < x:
                p1_next = p1.next
                p1.next = p
                p1 = p1.next
                p1.next = p1_next
            else:
                if not p2:
                    p1.next = p
                    p2 = p1.next
                else:
                    p2.next = p
                    p2 = p2.next

            p = next

        return ans.next