Monday, August 17, 2015

Linked list: Pairwise swap

private static void SwapEveryTwoNodes(LinkedList l)
        {
            if (l == null || l.head == null)
                return;
            Node cur = l.head;
            Node next = cur.next;
            Node pre = null;
            if (cur == null || next == null)
                return;
            l.head = l.head.next;
            //in every iteration, there should be minimum 3 pointer change. Before next iteration begins,
            //ensure that the pointer to previos node is saved.           
          
            while (cur != null && next != null)
            {
                // cur =1, next = 2
                cur.next = next.next; //1.next=3
                next.next = cur; // 2.next=1
                if(pre!=null) // this check is only for first iteration
                    pre.next = next; //connect the left side of the LL with the swapped nodes
                pre = cur; //Save previous step
                cur = cur.next; //next odd numbered node
                next = cur!=null? cur.next:null; //next even numbered node              
            }
        }

No comments:

Post a Comment