链表划分

题目

给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。

你应该保留两部分内链表节点原有的相对顺序。

http://www.lintcode.com/zh-cn/problem/partition-list/#

分析

可以创建两个链表,一个用来存储比x小的值,剩下的值存在另一个链表,最后将两个链表合并,就是需要的结果。合并链表时,考虑一下特殊情况即可。

代码


/**
 * 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
        if(head == null ){
            return null;
        }
        ListNode lhead,ltail, ohead, otail;
        
        lhead = ltail = ohead = otail = null;
        
        for(; head != null; head = head.next){
            if(head.val < x){
                if(lhead == null){
                    lhead = new ListNode(head.val);
                    ltail = lhead;
                }else{
                    ltail.next = new ListNode(head.val);
                    ltail = ltail.next;
                }
            }else{
                if(ohead == null){
                    ohead = new ListNode(head.val);
                    otail = ohead;
                }else{
                    otail.next = new ListNode(head.val);
                    otail = otail.next;
                }
            }
        }
        
        if(lhead == null){
           return ohead;
        }else{
           ltail.next = ohead;
        }
        return lhead;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.