Adobe Interview Question
SDE-2sCountry: United States
Check this out:
void PairWiseSwap(Node** mainlist)
{
if (mainlist && *mainlist)
{
Node* list = *mainlist;
Node* temp = list->next;
if (temp)
{
*mainlist = temp;
while(temp)
{
list->next = temp->next;
temp->next = list;
temp->prev = list->prev;
list->prev = temp;
if (temp->prev)
temp->prev->next = temp;
if (list ->next)
list ->next->prev = list ;
list = temp->next;
if (list)
temp = list->next;
else
temp = 0;
}
}
}
}
answer suggestion:
public Node SwapPairWise(Node list)
{
Node nextList=null,prev=null,next=null,cur=null;
if(list!=null)
{
cur=list;
}
else
{
return null;
}
list=cur.Next;
while(cur!=null)
{
nextList=cur.Next.Next;
prev=cur.Prev;
next=cur.Next;
next.Next=cur;
cur.Prev=next;
cur.Next=nextList;
if(nextList!=null)
{
nextList.prev=cur;
}
next.Prev=prev;
if(prev!=null)
{
prev.Next=next;
}
cur=nextList;
}
return list
}
This is a modified version of reversing a doubly linked list. At the end we traverse back to the beginning to update the head node.
public void swapPairsInList(Node head) {
if (head == null || head.next == null) {
return; // 0 or 1 node
}
Node p;
Node q;
Node r = head;
while (r != null && r.next != null) {
p = r;
q = r.next;
r = q.next;
q.prev = p.prev;
if (p.prev != null) {
p.prev.next = q;
}
p.prev = q;
p.next = q.next;
if (q.next != null) {
q.next.prev = p;
}
q.next = p;
}
while(p.prev != null) {
p = p.prev;
}
this.head = p;
}
HERE,
A<=>B<=>C
then for iteration 1 A is startp and B is endp;
for iteration 2 C is startp and endp is null. Hence, break;
At the end, end is travesed till right head position.
void SwapPairElements()
{
if(head == 0)
return;
else
{
Node *startp = head;
Node *endp = null;
while(startp)
{
endp = startp->next;
if(endp)
{
startp->next = endp->next;
endp->next = startp;
endp->prev = startp->prev;
startp->prev = endp;
if(startp->next)
startp->next->prev = startp;
if(endp->prev)
endp->prev->next = endp;
startp = startp->next;
}
else {
endp = startp;
break;
}
}
}
while(endp->prev != null)
endp= endp>prev;
head = endp;
}
node* swapPair(struct node *head)
{
if(!head || !(head->next))
return head;
struct node* curr=head;
struct node* succ=curr->next->next;
curr->next->next=curr;
curr->prev=curr->next;
curr->next=swapPair(succ);
curr->prev->prev=NULL;
if(curr->next)
curr->next->prev=curr;
return (curr->prev);
}
I generalized the solution to swap every 'k' elements:
public static Node swapKElements(Node head, int k) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
Node current = head;
Node next = head.next;
current.next = null;
current.prev = null;
int i = 0;
while (next != null && i < k - 1) {
Node temp = next.next;
next.next = current;
next.prev = current.prev;
current.prev = next;
current = next;
next = temp;
i++;
}
if (next != null) {
head.next = swapKElements(next, k);
if (head.next != null) {
head.next.prev = head;
}
}
return current;
}
- Santhosh Kumar May 10, 2013