MENU

LeetCode86. 分隔链表

August 8, 2018 • Read: 2643 • LeetCode阅读设置

题目链接:LeetCode86

题解

这道题类似荷兰国旗,说一下做法,最简单的方法就是直接将所有的值保存到数组中,然后对数组进行划分,完了以后再重新插回链表中。但是这道题有一个附加要求,要保留每个节点的相对位置,所以这道题应该这么做,首先创建4个节点,分别是ps,pe,qs,qe,然后遍历一遍链表,每次遍历到的当前值cur如果小于指定的值,就将其插到p节点中去,否则就插到q节点中去

代码
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
class Solution {
    public ListNode partition(ListNode Head, int x) {
        ListNode ps = null;//p start
        ListNode pe = null;//p end
        ListNode qs = null;//q start
        ListNode qe = null;//q end
        ListNode current = Head;
        while(current != null) {
            ListNode temp = current.next;
            current.next = null;
            if(current.val < x) {
                if(ps == null) {
                    ps = current;
                    pe = current;
                }
                else {
                    pe.next = current;
                    pe = current;
                }
            }
            else{
                 if(qs == null) {
                    qs = current;
                    qe = current;
                }
                else {
                    qe.next = current;
                    qe = current;
                }
            }
            current = temp;
        }
        if(ps == null)
            return qs;
        pe.next = qs;
        return ps;
    }
}
Last Modified: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code