JavaScript分隔链表问题怎么解决
这篇文章主要介绍“JavaScript分隔链表问题怎么解决”,在日常操作中,相信很多人在JavaScript分隔链表问题怎么解决问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”JavaScript分隔链表问题怎么解决”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
光泽网站建设公司创新互联,光泽网站设计制作,有大型网站制作公司丰富经验。已为光泽成百上千提供企业网站建设服务。企业网站搭建\成都外贸网站建设公司要多少钱,请找那个售后服务好的光泽做网站的公司定做!
原题
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
解题
题目很好理解,重点在于区分大于等于和小于目标值的节点,判断其实是很简单的,主要在于如何拼接链表,以及最终如何返回。
我发现,针对链表拼接的这种题目,常常可以通过添加辅助节点(辅助头结点或者辅助尾结点)来简化拼接操作。
这道题的话,需要针对两个区间都添加辅助头结点和尾结点,然后利用一个 current 节点进行遍历,扫描到大于等于目标值的节点,添加到相应区间的尾结点,再将尾结点后移;小于目标值的节点,添加到相应区间的尾结点,再将尾结点后移。
遍历完成后,利用辅助节点将两个区间拼接,再返回。让我们看下代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
// 小于x的节点,开始节点和结束节点
ListNode lessStart = new ListNode(0);
ListNode lessEnd = lessStart;
// 大于等于x的节点,开始节点和结束节点
ListNode moreStart = new ListNode(0);
ListNode moreEnd = moreStart;
// 利用current节点扫描
ListNode current = head;
while (current != null) {
// 小于x的节点
if (current.val < x) {
// 添加到相应区间的尾结点,再将尾结点后移
lessEnd.next = current;
lessEnd = current;
}
// 大于等于x的节点
else {
// 添加到相应区间的尾结点,再将尾结点后移
moreEnd.next = current;
moreEnd = current;
}
current = current.next;
}
// 将两个区间拼接
lessEnd.next = moreStart.next;
// 需要让最终尾结点指向null,因为该尾结点不一定是原链表尾结点,如果指向别的节点,可能会造成循环链表
moreEnd.next = null;
// 返回现在的头结点
return lessStart.next;
}
}
提交OK,执行用时:1 ms
,内存消耗:35.9 MB
。
到此,关于“JavaScript分隔链表问题怎么解决”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!
分享题目:JavaScript分隔链表问题怎么解决
分享链接:http://scyanting.com/article/jepdcs.html