第86题:分隔链表

一. 问题描述

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3

输出: 1->2->2->4->3->5

二. 解题思路

本题思路:采用双指针的方法进行求解,并且需要了解如何链表如何交换节点。

步骤一:first指针指向小于目标值x的节点,而second指针指向first的下一个节点。

步骤二:从second指针指向的节点开始遍历,找到下一个小于目标值x的节点。

步骤三:将找到小于目标值x的节点插入到first指针的后一个节点中(百度如何交换链表节点)。将first指向first.next节点,返回步骤二。

(在这里第三步有一个简单方法,接着将将first指向first.next节点,second指向second.next节点,继续返回步骤三,会比较简单点。)

三. 执行结果

执行用时 :1 ms, 在所有 java 提交中击败了88.29%的用户

内存消耗 :35.6 MB, 在所有 java 提交中击败了57.14%的用户

四. Java代码

class Solution {
    public ListNode partition(ListNode head, int x) {
         
         if(head==null)
         {
             return head;
         }
         ListNode first=new ListNode(0);
         first.next=head;
         ListNode second=first;
         ListNode result=first;
         while(second.next!=null&&first.next!=null)
         {
             if(first.next.val<x)
             {
                 first=first.next;
             }else
             {
                    second=first.next; 
                while(second.next!=null&&second.next.val>=x)
                {
                    second=second.next;
                }
                ListNode temp=second.next;
                if(temp==null)
                {
                    return result.next;
                }
                second.next=temp.next;
                temp.next=first.next;
                first.next=temp;
                first=first.next;
             }
         }
         
         return result.next;
            
    }
}

 

上一篇:csp-s模拟86


下一篇:牛客练习赛86