ChatGPT刷力扣面试题 02.04. 分割链表（可用于区分奇偶节点）

直播截图

开始解题（Java+python）

java代码

实际应用

这个函数可以用于将一个链表按照某个特定值 x 进行分区。可以将小于 x 的节点放在前面，大于等于 x 的节点放在后面。

这个函数的实际应用可以是解决一些与链表相关的问题。例如，给定一个链表，要求将链表中的奇数节点和偶数节点分开，并保持它们的相对顺序不变。可以使用这个函数来将链表分为两个部分，其中一个部分包含奇数节点，另一个部分包含偶数节点。

另一个例子是，给定一个链表，要求将链表分为三个部分，其中一个部分包含小于 x 的节点，另一个部分包含等于 x 的节点，最后一个部分包含大于 x 的节点。可以使用这个函数来实现这个功能。

逐步验算

 首先，给定输入为 head = [1,4,3,2,5,2], x = 3。初始化 smallHead、smallTail、largeHead、largeTail 指针：smallHead = ListNode(0)
smallTail = smallHead
largeHead = ListNode(0)
largeTail = largeHead进入循环，遍历链表 head：当 head = 1 时，1 < 3，将该节点插入到小链表中：smallTail.next = head，即 smallHead.next = 1
smallTail = smallTail.next，即 smallTail = 1当 head = 4 时，4 >= 3，将该节点插入到大链表中：largeTail.next = head，即 largeHead.next = 4
largeTail = largeTail.next，即 largeTail = 4当 head = 3 时，3 >= 3，将该节点插入到大链表中：largeTail.next = head，即 largeHead.next = 4 -> 3
largeTail = largeTail.next，即 largeTail = 3当 head = 2 时，2 < 3，将该节点插入到小链表中：smallTail.next = head，即 smallHead.next = 1 -> 2
smallTail = smallTail.next，即 smallTail = 2当 head = 5 时，5 >= 3，将该节点插入到大链表中：largeTail.next = head，即 largeHead.next = 4 -> 3 -> 5
largeTail = largeTail.next，即 largeTail = 5当 head = 2 时，2 < 3，将该节点插入到小链表中：smallTail.next = head，即 smallHead.next = 1 -> 2 -> 2
smallTail = smallTail.next，即 smallTail = 2遍历完链表后，将大链表的尾节点指向 null，即 largeTail.next = null，此时大链表为 4 -> 3 -> 5 -> null。
将小链表的尾节点指向大链表的头节点，即 smallTail.next = largeHead.next，此时小链表为 1 -> 2 -> 2 -> 4 -> 3 -> 5 -> null。
返回小链表的头节点，即 smallHead.next，即返回链表 1 -> 2 -> 2 -> 4 -> 3 -> 5 -> null。最终输出为 [1, 2, 2, 4, 3, 5]，符合预期结果。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！