链表划分

链接

给定一个链表,再给定一个整数 pivot,请将链表调整为左部分都是值小于 pivot 的节点,中间部分都是值等于 pivot 的节点, 右边部分都是大于 pivot 的节点。
除此之外,对调整后的节点顺序没有更多要求。

import java.util.Scanner;

public class Main {

    static class Node {
        Node next;
        int val;

        public Node(int val) {
            this.val = val;
        }
    }


    private static Node solve(Node head, int pivot) {
        if (head == null || head.next == null) {
            return head;
        }

        Node lessHead = null;
        Node lessTail = null;
        Node equalHead = null;
        Node equalTail = null;
        Node moreHead = null;
        Node moreTail = null;

        Node cur = head, next;

        while (cur != null) {
            next = cur.next;
            cur.next = null;
            if (cur.val < pivot) {
                if (lessTail == null) {
                    lessHead = cur;
                    lessTail = cur;
                } else {
                    lessTail.next = cur;
                    lessTail = cur;
                }
            } else if (cur.val == pivot) {
                if (equalTail == null) {
                    equalHead = cur;
                    equalTail = cur;
                } else {
                    equalTail.next = cur;
                    equalTail = cur;
                }
            } else {
                if (moreTail == null) {
                    moreHead = cur;
                    moreTail = cur;
                } else {
                    moreTail.next = cur;
                    moreTail = cur;
                }
            }
            cur = next;
        }

        if (lessTail != null) {
            lessTail.next = equalHead;
            if (equalTail == null) {
                equalTail = lessTail;
            }
        }

        if (equalTail != null) {
            equalTail.next = moreHead;
        }

        return lessHead == null ? (equalHead == null ? moreHead : equalHead) : lessHead;

    }

    private static void print(Node node) {
        StringBuilder res = new StringBuilder();
        while (node != null) {
            res.append(node.val).append(" ");
            node = node.next;
        }
        System.out.println(res.subSequence(0, res.length() - 1));
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int pivot = in.nextInt();
            Node head = new Node(in.nextInt());
            Node pre = head;
            while (--n > 0) {
                Node node = new Node(in.nextInt());
                pre.next = node;
                pre = node;
            }
            Node node = solve(head, pivot);
            print(node);
        }
    }
}
上一篇:总结篇3-python数据结构和算法


下一篇:排序算法