Monday, August 08, 2016

split linked list by even and odd nodes

(head):
    n = head
    evenhead = n
    if n != null:
        oddhead = n.next
    even = odd = null
    i = 0
    while n != null:
        if i == 0:
            if even != null:
                even.next = n
            even = n
        else:
            if odd != null:
                odd.next = n
            odd = n
        n = n.next
        i = (i+1) &1
    if even != null:
        even.next = null
    if odd != null:
        odd.next = null
    return evenhead, oddhead
Better is to jump 2 nodes.
split(head):
    if head == null:
        throw
    ehead = e = head
    ohead = o = head.next
    while e?.next != null && o?.next != null:
        e.next = e.next.next
        e = e.next
        o.next = o.next.next
        o = o.next
    if e != null:
        e.next = null
    if o != null: // not required
        o.next = null
    return {ehead, ohead}
[Hat tip to MA]

No comments:

Post a Comment