Microsoft Interview Question Interns
Team: Bing-Appex
Country: United States
Interview Type: In-Person
You could try using a Stack
static void Reverse(SimpleList L, int n)
{
if (L == null || n < 0)
throw new ArgumentException();
if (L.Count < 2 || n < 2)
return;
var S = new Stack<SimpleListNode>(n);
SimpleListNode prev = null;
SimpleListNode current = L.Head;
while (current != null)
{
var Next = current.Next;
if (S.Count < n)
S.Push(current);
if (S.Count >= n || current.Next == null)
{
if (prev != null)
prev.Next = S.Peek();
else
L.Head = S.Peek();
while (S.Count > 0)
{
if (S.Count == 1)
prev = S.Peek();
var item = S.Pop();
if (S.Count > 0)
item.Next = S.Peek();
else
item.Next = null;
}
}
current = Next;
}
}
import java.util.Stack;
public class ReverseLinkedListInParts {
Node head;
int size;
class Node {
int value;
Node next;
public Node(int value) {
super();
this.value = value;
this.next = null;
}
}
public ReverseLinkedListInParts() {
super();
head = null;
size = 0;
}
public void add(int e) {
Node newnode = new Node(e);
if (head == null) {
head = newnode;
size++;
return;
}
Node ptr = head;
while (ptr.next != null) {
ptr = ptr.next;
}
ptr.next = newnode;
size++;
}
public void reverseInPart(int parts) {
if (parts > size || parts < 1) {
System.out.println("The part is out of range. Cannot reverse");
return;
}
Node headPtr = head;
while (headPtr != null) {
int n = parts;
Node tailPtr = headPtr;
while (n > 1 && tailPtr.next != null) {
tailPtr = tailPtr.next;
n--;
}
reverse(headPtr,tailPtr);
headPtr = tailPtr.next;
}
}
private void reverse(Node headPtr, Node tailPtr) {
Stack<Integer> stack = new Stack<Integer>();
Node ptr = headPtr;
while(ptr != tailPtr){
stack.push(ptr.value);
ptr = ptr.next;
}
stack.push(tailPtr.value);
ptr = headPtr;
while(ptr != tailPtr){
ptr.value = stack.pop();
ptr = ptr.next;
}
tailPtr.value = stack.pop();;
}
public void print() {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.value + "\t");
ptr = ptr.next;
}
System.out.println();
}
public static void main(String[] args) {
ReverseLinkedListInParts ll = new ReverseLinkedListInParts();
ll.add(3);
ll.add(1);
ll.add(5);
ll.add(7);
ll.add(2);
ll.add(4);
ll.add(6);
ll.print();
ll.reverseInPart(8);
ll.print();
}
}
public Node reverseN(Node first, int N, Node zero) {
Node current = first;
Node previous = null;
for(int i=0;i<N && current != null;i++) {
Node t = current.next;
current.next = previous;
previous = current;
current = t;
}
//done when first.next == null;
first.next = current;
if(zero != null) {
zero.next = previous;
}
return previous;
}
public Node reverseParts(Node start, int N) {
Node output = reverseN(start,N,null);
while(start.next != null) {
Node t = start;
start = start.next;
reverseN(start,N,t);
}
return output;
}
struct Node
{
int data;
struct Node *next;
};
struct Node *NewNode(int data)
{
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=data;
temp->next=NULL;
return temp;
}
struct Node *Reverse(struct Node *node,int k)
{
if(!node)
return NULL;
struct Node *temp=node;
struct Node *p=node,*r=NULL,*q;
int len=k;
while(len-- && p)
{
q=r;
r=p;
p=p->next;
r->next=q;
}
node->next=Reverse(p,k);
return r;
}
int main()
{
struct Node *node=NewNode(1);
node->next=NewNode(2);
node->next->next=NewNode(3);
node->next->next->next=NewNode(4);
node->next->next->next->next=NewNode(5);
node->next->next->next->next->next=NewNode(6);
node->next->next->next->next->next->next=NewNode(7);
node->next->next->next->next->next->next->next=NewNode(8);
int k=3;
struct Node *res=Reverse(node,k);
getchar();
return 0;
}
Would recommend you to draw the linked list example given and understand.
void step_reverse_list(struct node **head,int step)
{
struct node *prev=NULL,*will_visit_next,*iterator=*head,start_node;
struct node *sixth_prev_node=&start_node,*third_prev_node; //create a fake start_node so as to get the start node inside the general loop
int n=step;
while(iterator->next!=NULL)
{
if(n%step==0)
third_prev_node = iterator; //store this node, as we will need to modify its next later
if(n%step==1)
{
sixth_prev_node->next=iterator; //this is the node which should be pointed by the 6th previous node
sixth_prev_node = third_prev_node; //transfer the 3rd previous node
n = step+1; //increase step by n+1 as step -- occurs in the end
}
will_visit_next = iterator->next;
iterator->next = prev;
prev = iterator;
iterator = will_visit_next;
n--;
}
iterator->next=prev; //normal reversal technique
sixth_prev_node->next = iterator; //this is the node that the 6th previous or the node between the 3rd and 6th prev should point to (originnally the last node)
third_prev_node->next = NULL; //the 3rd previous or 2nd or previous node should be the last element in the new linked iterator
*head = start_node.next; //we now modify the head to be the next pointer of the fake start_node we created for the sake of generality
}
So I see everyone doing pointer manipulations (setting the next of one to the next of another), but I figured that if you have access to the Node (and its parts), why not leave the list intact and instead move the values around?
struct Node {
int value;
struct Node *next;
} typedef Node;
public Node reverse(int parts, Node list) {
int[] nums = malloc(sizeof(int) * parts);
Node* current = list;
Node* temp = list;
while(current != null) {
for(int i = 0; i < parts; i++) {
nums[i] = temp->value;
temp = temp->next;
if(temp = null)
break;
}
temp = current;
for(int i = 0; i < parts; i++) {
temp->value = nums[i];
temp = temp->next;
if(temp = null)
break;
}
current = temp;
}
}
pardon my C, it's not the best
#include <stdio.h>
#include <conio.h>
typedef struct NODE
{
int data;
struct NODE *next;
}*PNODE,NODE;
void printList(PNODE head)
{
printf("\nLinked List ");
while(head)
{
printf(" -> %d", head->data);
head = head -> next;
}
}
PNODE getNode(int data)
{
PNODE node = (PNODE)malloc(sizeof(NODE));
node -> data = data;
node -> next = NULL;
return node;
}
void delNode(PNODE node)
{
free(node);
node = NULL;
}
void createList(PNODE head)
{
int i = 0;
for(i = 1; i< 10; i++)
{
head -> next = getNode(i);
head = head->next;
}
}
PNODE revList(PNODE head, int len)
{
PNODE current = head;
PNODE next = NULL;
PNODE newHead = NULL;
int i = 0;
while(current && i < len)
{
next = current->next;
current->next = newHead;
newHead = current;
current = next;
i++;
}
next = newHead;
while(next -> next)
{
next = next -> next;
}
next->next = current;
return newHead;
}
int main()
{
PNODE head = getNode(0);
PNODE newHead = NULL;
clrscr();
createList(head);
printList(head);
newHead = revList(head, 3);
printList(newHead);
getch();
return 0;
}
public Items ReverseLinkedListInParts(int n)
{
Items start = Head;
Items temp;
Items previous = null;
Items current = null;
int count = 0;
while (start != null)
{
if (count < n)
{
temp = start.next;
start.next = previous;
previous = start;
start = temp;
count++;
if (start == null)
{
current = AddNext(current, previous);
}
}
else
{
current = AddNext(current, previous);
previous = null;
count = 0;
}
}
return current;
}
public Items AddNext(Items previous,Items newItem)
{
Items current = previous;
if (previous == null)
{
return newItem;
}
while (previous.next != null)
{
previous = previous.next;
}
previous.next = newItem;
return current ;
}
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* BuildLinkedList();
void PrintResult(Node*);
int main()
{
Node* root = BuildLinkedList();
Node* result = NULL;
Node* start = NULL;
int stack[3];
int stackPointer = 0;
for(int i=1; root != NULL; i++, root = root ->next)
{
stack[stackPointer ++] = root -> data;
if(( i % 3 == 0) || (root -> next == NULL))
{
stackPointer = 0;
for(int i= 3-1; i>= 0; i--)
{
if(stack[i] != 1366047854)
{
Node* node = new Node();
node -> data = stack[i];
node -> next = NULL;
if(start==NULL)
{
start = node;
result = start;
}
else
start->next = node;
start = node;
stack[i] = 1366047854; //assigning some unique to mark stack bottom
}
}
}
}
PrintResult(result);
}
void PrintResult(Node* root)
{
for(Node* i = root; i != NULL; i= i->next)
cout << i -> data << " ";
}
Node* BuildLinkedList()
{
Node* start = NULL;
Node* root = NULL;
int i = 1;
while(i <= 8)
{
Node* node = new Node();
node->data = i;
node->next = NULL;
if(start==NULL)
{
start = node;
root = start;
}
else
start->next = node;
start = node;
i++;
}
return root;
}
void List :: reverse(int c)
{
List *prev = NULL,*temp = first,*ptr = NULL,*tail = NULL,*tempVar = temp;
int count = 0;
while(tempVar != NULL)
{
ptr = temp -> next;
temp -> next = prev;
prev = temp;
++count;
temp = ptr;
if (count == c || (temp == NULL && count < c))
{
first = prev;
}
if (count % c == 0 || temp == NULL)
{
if (tail != NULL)
{
tail -> next = prev;
}
tail = tempVar;
tempVar = temp;
prev = NULL;
}
}
}
:)
#include <stdio.h>
#include <conio.h>
typedef struct NODE
{
int data;
struct NODE *next;
}*PNODE,NODE;
void printList(PNODE head)
{
printf("\nLinked List ");
while(head)
{
printf(" -> %d", head->data);
head = head -> next;
}
}
PNODE getNode(int data)
{
PNODE node = (PNODE)malloc(sizeof(NODE));
node -> data = data;
node -> next = NULL;
return node;
}
void delNode(PNODE node)
{
free(node);
node = NULL;
}
void createList(PNODE head)
{
int i = 0;
for(i = 1; i< 10; i++)
{
head -> next = getNode(i);
head = head->next;
}
}
PNODE revList(PNODE head, int len)
{
PNODE current = head;
PNODE next;
PNODE prev = NULL;
PNODE newHead = NULL;
PNODE newTail = NULL;
int i = 0;
while(current)
{
i = 0;
prev = NULL;
while(current && i < len)
{
next = current -> next;
current -> next = prev;
prev = current;
current = next;
i++;
}
if(newHead == NULL)
{
newHead = prev;
}
else
{
newTail = newHead;
while(newTail -> next)
newTail = newTail -> next;
newTail -> next = prev;
}
}
return newHead;
}
int main()
{
PNODE head = getNode(0);
PNODE newHead = NULL;
clrscr();
createList(head);
printList(head);
newHead = revList(head, 4);
printList(newHead);
getch();
return 0;
}
use a recursive solution. I think it will be much easier in way of thinking.
import java.util.Scanner;
//partition a linked list around value x
//
class Node{
public int value;
public Node next;
public Node(Node prev, int _value){
this.value = _value;
if(prev == null)
return;
prev.next = this;
next = null;
return;
}
}
public class ReversePart{
public static void printNodes(Node head){
Node traverser = head;
while(traverser != null){
System.out.print(traverser.value + " ");
traverser = traverser.next;
}
}
public static Node reversePart(Node head, int part){
if(head == null || head.next == null)
return head;
int count = 0;
Node pre = head;
Node later = head.next;
Node next = null;
while(count < part - 1 && later != null){
next = later.next;
later.next = pre;
pre = later;
later = next;
count ++;
}
if(next != null){
head.next = reversePart(next, part);
}
//important
if(next == null){
//termination condition
//no sufficient elements
head.next = null;
}
return pre;
}
public static final void main(String[] args){
Scanner scanner = new Scanner("1 2 3 4 5 6 7 8 9 10 11");
Node head = null;
Node prev = null;
while(scanner.hasNext()){
if(prev == null){
head = new Node(prev, scanner.nextInt());
prev = head;
}
else
prev = new Node(prev, scanner.nextInt());
}
Node newHead = ReversePart.reversePart(head,3);
ReversePart.printNodes(newHead);
return;
}
}
// list will be reversed by subPart,
// eg. if list is as follow and subPart is 3 then
// head -> A -> B -> C -> D -> E -> F -> G -> H
// head -> C -> B -> A -> F -> E -> D -> H -> G
void Reverse_Partial(int subPart)
{
if (m_head == 0 || m_size == 1 || subPart == 1)
return;
List_Node_Ptr cur = m_head; // current node
List_Node_Ptr prev = 0; // will maintain prev node
List_Node_Ptr next = 0; // will maintain next node
List_Node_Ptr lastTail = 0; // will maintain last tail node
int numIter = m_size/subPart; // will maintain how many sub part of given array will be made.
int ni = 0;
int i = 0;
bool firstTime = true; // will use only once to set the m_head
// we will proceed as follow
// 1. will iterate over each sub part
// 2. reverse the sub partial list
// 3. will change lastTail node pointer of previos reversed linked list,
// 4. if we are reversing first sub part linked list then change m_head node
// 5. reset the variables
// step 1
while (ni <= numIter) {
// step 2
while (cur != 0 && i < subPart) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
++i;
}
// step 3
if (lastTail == 0) {
lastTail = m_head;
}
else {
lastTail->next = prev;
// make sure Tail->next pointer will be null, so that we can add next reversed partial list
while(lastTail->next != 0) {
lastTail = lastTail->next;
}
}
// step 4
if (firstTime) {
firstTime = false;
m_head = prev;
}
// step 5
i = 0;
++ni;
prev = 0;
}
}
private static Node reverseALinkedList(Node root, int k) {
Node current = root;
Node prev = null;
Node next = null;
int i = 0;
while(current != null && i != k){
next = current.next;
current.next = prev;
prev = current;
current = next;
i++;
}
if(next != null){
root.next = reverseALinkedList(next, k);
}
return prev;
}
I also use stack, and write in java. The code is short and pass the example above. I wonder if there are bugs. Plz comment if you find some.
public static ListNode reverseList(ListNode node, int n)
{
ListNode head = new ListNode(0);
ListNode current = head;
Stack<ListNode> stack = new Stack<ListNode>();
while (node != null)
{
if (stack.size() < n)
{
stack.push(node);
node = node.next;
continue;
}
while (!stack.isEmpty())
{
current.next = stack.pop();
current = current.next;
}
}
while (!stack.isEmpty())
{
current.next = stack.pop();
current = current.next;
}
current.next = null;
return head.next;
}
static Node ReverseBlocksLinkedList(Node root, int portion)
{
int i = 1;
Node preRoot = null;
Node preNode = null;
Node curNode = root;
Node curRoot = null;
while (curNode != null)
{
curRoot = curNode;
while (i <= portion && curNode != null)
{
preNode = curNode;
curNode = curNode.Next;
i++;
}
preNode.Next = preRoot;
preRoot = curRoot;
i = 1;
}
return curRoot;
}
static Node ReverseWholeLinkedList(Node root)
{
Node cur = root;
Node next = null;
Node pre = null;
while (cur != null)
{
//Set the next to point to item next to current
next = cur.Next;
//reset the cur next to point to pre node
cur.Next = pre;
//make cur to be pre;
pre = cur;
//make cur node to be next
cur = next;
}
return pre;
}
/*C# implementation*/
static LinkNode ReverstLinkListByN(LinkNode Head, int n)
{
LinkNode newHead = null;
LinkNode nHead = null, pre = null, cur = null, next = null, nTail = null, OldTail = null;
int count = 0;
if (Head != null)
{
cur = Head;
while (cur != null)
{
if (pre == null)
{
pre = cur;
cur = cur.Next;
nTail = pre;
count++;
}
else
{
next = cur.Next;
cur.Next = pre;
pre = cur;
cur = next;
count++;
}
if (count == n || cur == null)
{
nHead = pre;
if (newHead == null) newHead = nHead;
if (OldTail != null)
{
OldTail.Next = nHead;
}
OldTail = nTail;
//start to reset
count = 0;
pre = null;
}
}
nTail.Next = null;
}
return newHead;
}
/*C# implementation*/
static LinkNode ReverstLinkListByN(LinkNode Head, int n)
{
LinkNode newHead = null;
LinkNode nHead = null, pre = null, cur = null, next = null, nTail = null, OldTail = null;
int count = 0;
if (Head != null)
{
cur = Head;
while (cur != null)
{
if (pre == null)
{
pre = cur;
cur = cur.Next;
nTail = pre;
count++;
}
else
{
next = cur.Next;
cur.Next = pre;
pre = cur;
cur = next;
count++;
}
if (count == n || cur == null)
{
nHead = pre;
if (newHead == null) newHead = nHead;
if (OldTail != null)
{
OldTail.Next = nHead;
}
OldTail = nTail;
//start to reset
count = 0;
pre = null;
}
}
nTail.Next = null;
}
return newHead;
}
node* reverseByParts(node *head, int N)
{
if (head == NULL)
return head;
bool firstPart = true;
node* newHead = NULL;
node* cur = head;
node* pre = NULL;
node* first1 = head;
node* first2 = NULL;
node* next = NULL;
int i;
while (cur != NULL) {
first2 = first1;
first1 = cur;
//cout<<"##"<<first1->val<<endl;
//cout<<"#2#"<<first2->val<<endl;
for (i = 0; i < N && cur != NULL; cur = next, i++) {
next = cur->next;
if (cur != first1) {
cur->next = pre;
//cout<<cur->val<<" to "<<pre->val<<endl;
}
pre = cur;
}
if (firstPart == true) {
newHead = pre;
firstPart = false;
}
else {
//cout<<first2->val<<" to "<<pre->val<<endl;
first2->next = pre;
}
pre = first1;
}
pre->next = NULL;
return newHead;
}
A solution in Java with test cases. I use two while loops. Each time I reverse the next n nodes. I do not use stack to save space, because we can always reverse a list by inserting the next node after the new head node. Time O(n), Space O(1).
public class LinkedListNode
{
public LinkedListNode next=null;
public int val=Integer.MIN_VALUE;
public LinkedListNode(int v)
{
this(v, null);
}
public LinkedListNode(int v, LinkedListNode node)
{
val=v;
next=node;
}
public String toString()
{
return String.format("[LinkedListNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[LinkedListNode: val=%d, next=%s]", val, (next!=null) ? next.toStringAll() : null);
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5,
new LinkedListNode(6))))));
System.out.println(head.toStringAll());
}
}
public class ID15138683
{
public LinkedListNode reverse(LinkedListNode head, int n)
{
LinkedListNode newHead=new LinkedListNode(-1);
LinkedListNode tail=newHead;
LinkedListNode node=head;
LinkedListNode tempHead=newHead;
while (node!=null)
{
int index=0;
while (node!=null && index<n)
{
if (tempHead.next==null)
tail=node;
// insert node after tempHead to finally get a reversed list of the n nodes
LinkedListNode nextNode=node.next;
node.next=tempHead.next;
tempHead.next=node;
node=nextNode;
index++;
}
tempHead=tail;
}
return newHead.next;
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5,
new LinkedListNode(6,
new LinkedListNode(7)))))));
System.out.println(head.toStringAll());
ID15138683 wpd=new ID15138683();
System.out.println(wpd.reverse(head, 3).toStringAll());
System.out.println(wpd.reverse(null, 1));
}
}
Total Time Complexity O(3n)
Total Space Complexity O(2n)
Approach.
1. Create a SplitList function with O(n) Time and O(n) Space.
2. Create a ReverseList function with O(n)
3. Create a MainLogic Function with O(n) Time and O(n) Space and call the above 2 methods.
Basic Tested and working code in C#. Need to test all edge cases.
public List<Node> SplitList(Node currentNode, int splitCnt)
{
int lpCnt = 1;
List<Node> listCollection = new List<Node>();
Node tempParent = null;
Node tempNodeHead = null;
Node tempNode = null;
// Repat loop till end of list.
while (currentNode != null)
{
if (lpCnt == 1)
{
tempNodeHead = new Node();
tempNodeHead.NodeValue = currentNode.NodeValue;
tempParent = tempNodeHead;
}
// Since current node already added as parent them move the next node.
currentNode = currentNode.NextNode;
// Repeat loop till split count.
while (lpCnt <= splitCnt && currentNode != null)
{
tempNode = new Node();
tempNode.NodeValue = currentNode.NodeValue;
lpCnt++;
tempNodeHead.NextNode = tempNode;
tempNodeHead = tempNodeHead.NextNode;
currentNode = currentNode.NextNode;
}
listCollection.Add(tempParent);
lpCnt = 1;
}
return listCollection;
}
Node MakeListReverse(Node currentNode)
{
Node previousNode = null;
Node nextNode = null;
while (currentNode != null)
{
nextNode = currentNode.NextNode;
currentNode.NextNode = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
return previousNode;
}
/*
listSplit : 3
Input : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Output : 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7
*/
// Time Complexit : O(n) Space Complexity : O(n)
public Node ReverseLinkedListInParts(Node currentNode, int listSplit)
{
List<Node> listCollection = SplitList(currentNode, listSplit);
Node reversedMainList = new Node();
// Just a Pointer to the reversedMainList Head node, as reversedMainList is used for iteration.
Node reversedMainListHead = reversedMainList;
reversedMainListHead.NodeValue = 0; // Replace this at the end.
if (listCollection != null)
{
// O(SplitCnt) // Ignore
foreach (Node list in listCollection)
{
Node reversedSubList = MakeListReverse(list);
// O(n). For all sub child lists.
while (reversedMainList.NextNode != null)
{
reversedMainList = reversedMainList.NextNode;
}
reversedMainList.NextNode = reversedSubList;
}
}
// Replacing the zero.
reversedMainListHead = reversedMainListHead.NextNode;
return reversedMainListHead;
}
hope this is easier to read and/or correct
Update: Found bug, looking into it
node* reverseByParts(node* head, int parts)
{
if(head == null || head->next ==null )
{
return head;
}
else
{
node* localHead = head;
node* globalHead = null;
node* nodeBeingProcessed = head;
node* oldSuccessor = null;
node* oldPredecessor = null;
int nodesProcessed = 0;
while(nodeBeingProcessed != null)
{
while(nodesProcessed < parts && nodeBeingProcessed != null)
{
oldSuccessor = nodeBeingProcessed->next;
nodeBeingProcessed->next = oldPredecessor;
oldPredecessor = nodeBeingProcessed;
nodeBeingProcessed = oldSuccessor;
nodesProcessed++;
}
localHead->next = nodeBeingProcessed;
localHead = nodeBeingProcessed;
if(nodesProcessed == parts)
{
globalHead = oldPredecessor;
}
nodesProcessed = 0;
}
return newHead;
}
}
I was asked same Q at microsoft 2 years back. Few imp thing to keep in mind in Q like these:
1. Make no assumptions... ask wherever u have doubt before coding
2. Enumerate all cases and handle them when u write code like in this case inp could be of length 0,1,2,3n,3n+1,3n+2
3. Remember the head will change after this reversing so either use ptr to ptr while passing head or return the new head... as i have done in example below.
- vik January 15, 2013node* reversePartial(node* head){ if (head==NULL || head->next==NULL){ return head; //handling len 0 or 1 } node* newHead= NULL; bool firstTime = true; node * curr= head; node * nxt1 = head->next; node * nxt2 = nxt1->next; node * lastLoopItem = NULL; while (curr && nxt1 && nxt2){ //handling len = 3n node * ptr = nxt2->next; if (firstTime){ firstTime = false; newHead = nxt2; } if (lastLoopItem){ lastLoopItem->next= nxt2; } lastLoopItem = curr; nxt2->next = nxt1; nxt1->next = curr; curr->next = ptr; curr = ptr; if (curr){ nxt1 = curr->next; } else{ nxt1=nxt2=NULL; break; } if (nxt1){ nxt2 = nxt1->next; } else break; } if (nxt1){ //handling len=3n+2 if (firstTime){ newHead = nxt1; firstTime = false; } if (lastLoopItem) lastLoopItem->next= nxt1; nxt1->next=curr; curr->next=NULL; } if (lastLoopItem){ //handling len=3n+1 lastLoopItem->next= curr; } return newHead; }