Partition List

Partition List

今天是一道有关链表的题目，来自LeetCode，难度为Medium，Acceptance为27.9%。其实较为简单。

题目如下

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

该题的思路较为简单，类似于快排中的一次比较，即将小于x的数放在前面，大于等于x的数放在后面。可以用两个节点，分别指向小于和大于该数的链表的表头。然后将两个链表连在一起。

需要注意的是大数的链表的结尾要设置成null，否则有可能形成环。

代码如下

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        ListNode smaller = new ListNode(0), pSmaller = smaller;
        ListNode bigger = new ListNode(0), pBigger = bigger;
        for(ListNode p = head; p != null; p = p.next) {
            if(p.val < x) {
                smaller.next = p;
                smaller = p;
            } else {
                bigger.next = p;
                bigger = p;
            }
        }
        bigger.next = null;
        smaller.next = pBigger.next;
        return pSmaller.next;
    }
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image