2016-09-09 链表

[SnackMen]

86. Partition List 138. Copy List with Random Pointer

[dayang]

/**
 * [AC] LeetCode 86. Partition List
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    var dummyHead = new ListNode(0),p = dummyHead,q,temp;
    dummyHead.next = head;
    while(p.next !== null && p.next.val < x){
        p = p.next;
    }

    q = p;
    while(q.next !== null){
        if(q.next.val < x){
            temp = q.next;
            q.next = temp.next;
            temp.next = p.next;
            p.next = temp;
            p = p.next;
        }else{
            q = q.next;   
        }
    }

    return dummyHead.next;
};

[zhaokuohaha]

86 - C

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode Partition(ListNode head, int x) {
        if(head==null || head.next == null) return head;
        ListNode l,g,lh, gh;
        l = lh = new ListNode(0);
        g = gh = new ListNode(0);
        for(ListNode p = head; p != null;  p = p.next){
            if(p.val < x){ 
                l.next = p;
                l = l.next;
            }else{
                g.next = p;
                g = g.next;
            }
        }
        l.next = gh.next;
        g.next = null;
        return lh.next;
    }
}

[zhaokuohaha]

138 - C

/**
 * Definition for singly-linked list with a random pointer.
 * public class RandomListNode {
 *     public int label;
 *     public RandomListNode next, random;
 *     public RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode CopyRandomList(RandomListNode head) {
        if(head == null ) return null;
        RandomListNode cur = head,  next, copy;

        // 第一步,对于每个节都在其后面复制一份并插在原来节点后面
        while(cur != null){
            next = cur.next;
            copy = new RandomListNode(cur.label);
            copy.next = next;
            cur.next = copy;
            cur = next;
        }

        //第二步, 将原来节点的random信息复制到新建的节点中
        cur = head;
        while(cur != null){
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        //第三步, 分离源链表和复制的链表, 注意原链表的结构也要保存
        cur = head;
        RandomListNode res = new RandomListNode(0);
        copy = res;

        while(cur != null){
            copy.next = cur.next;
            copy = copy.next;
           cur.next = cur.next.next;
            cur = cur.next;
        }
        return res.next;
    }
}