Write a method switchPai rs that switches the order of elements in a linked list

Question

Write a method switchPairs that switches the order of elements in a linked list of integers in a pairwise fashion. Your method should switch the order of the first two values, then switch the order of the next two, switch the order of the next two, and so on. For example, if the list initially stores these values:

Your method should switch the first pair (3, 7), the second pair (4, 9), the third pair (8, 12), etc. to yield this list:

If there are an odd number of values, the final element is not moved. For example, if the list had been:

It would again switch pairs of values, but the final value (2) would not be moved, yielding this list:

Assume that we are adding this method to the LinkedIntList class as shown below. You may not call any other methods of the class to solve this problem, you may not construct any new nodes, and you may not use any auxiliary data structures to solve this problem (such as an array, ArrayList, Queue, String, etc.). You also may not change any data fields of the nodes. You must solve this problem by rearranging the links of the list.

Explanation / Answer

/** @param front Front node of the linked list

** @return front of the new list after switching pairs

**/

public ListNode switchPairs(ListNode front){

//first represents original first node

ListNode first = front;

//second represents original second node

//recursiveFront represents the first node of the

//list whose pairs are recursively switched

ListNode second,recursiveFront;

//We compute the second node only if first node is not empty

if(first!=null){

second = first.next;

//We recursively switch pairs only if second node is not empty

if(second != null){

//Recursively switchPairs for the rest of the list

recursiveFront = switchPairs(second.next);

//make the second Node as the new front node

front = second;

//Change its next pointer to the previous first node

front.next = first;

//Change the next pointer of previous first node to

//first node of recursively switched List

first.next = recursiveFront;

}

}

//Update the front of this list

this.front = front;

//Return the front node of this pair switched list

return front;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.