关于java:LeetCode086分隔链表

37次阅读

共计 1435 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有小于 x 的节点都呈现在大于或等于 x 的节点之前。

你该当保留两个分区中每个节点的初始绝对地位。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：链表遍历

申明 2 个链表 lessThan 和 moreThan 别离寄存小于 x 的节点和不小于 x 的节点，而后 2 个指针 curLess 和 curMore 别离指向 lessThan 和 moreThan 的头节点，而后遍历链表 head：

如果以后节点小于 x，则将以后节点增加到 lessThan 链表中；

如果以后节点不小于 x，则将以后节点增加到 moreThan 链表中。

链表 head 遍历实现后，将 lessThan 和 moreThan 的尾结点都指向 null，避免出现多余的节点，而后将 lessThan 的尾结点指向 moreThan 的头结点（行将小于 x 的节点挪到不小于 x 的节点的后面），最初返回 lessThan 的 next 节点即为最初后果。

public class LeetCode_086 {public static ListNode partition(ListNode head, int x) {
        // 小于 x 的链表节点
        ListNode lessThan = new ListNode(-1);
        // 不小于 x 的链表节点
        ListNode moreThan = new ListNode(-1);
        ListNode curLess = lessThan, curMore = moreThan;
        while (head != null) {if (head.val < x) {
                // 小于 x 的节点增加到链表 lessThan 中
                curLess.next = head;
                curLess = curLess.next;
            } else {
                // 不小于 x 的节点增加到链表 moreThan 中
                curMore.next = head;
                curMore = curMore.next;
            }
            head = head.next;
        }
        // 所有节点遍历实现后将 lessThan 和 moreThan 尾结点指向 null
        curLess.next = null;
        curMore.next = null;
        // 将小于 x 的节点挪到不小于 x 的节点的后面
        curLess.next = moreThan.next;
        return lessThan.next;
    }

    public static void main(String[] args) {ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);

        ListNode result = partition(head, 3);
        while (result != null) {System.out.print(result.val + " ");
            result = result.next;
        }
    }
}