C++ reordering Singly Linked List

Question

Hi I'm trying to write a code for singly linked list that reorders the nodes so that:

L1->L2->L3->...->Ln to L1->Ln->L2->Ln-1->L3->Ln-2...

So I tried to do this by finding the node at the end of the list and setting that node as the next of current node and then finishing the loop by setting the current node as the next next of current node.

#include <cstdlib>
#include <iostream>

using namespace std;

struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* newNode(int x){
    ListNode* temp = new ListNode;
    temp->val = x;
    temp->next = NULL;
    return temp;
}

void printlist(ListNode* head)
{
    while (head != NULL) {
        cout << head->val << " ";
        if (head->next)
            cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

void reorderList(ListNode* head){
    ListNode *curr = head;
    ListNode *temp=head;
    ListNode *last=NULL;
    while(curr->next != NULL){
        while(temp->next != NULL){
            temp=temp->next;
            last=temp;
        }
        curr->next=last;
        last->next=curr->next->next;
        curr=curr->next->next;
        temp=curr->next;
    }
}

int main(int argc, char** argv) {
    ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
 
    printlist(head); // Print original list
    reorderList(head); // Modify the list
    printlist(head); // Print modified list

    return 0;
}

So far, after displaying the original list, the program stops by saying that the run failed. I'm having some problem understanding the singly linked list and I don't know what I'm doing wrong.

L1->Ln->L2->Ln-1->L3->Ln-2... suggests the first node points to the last node which points to the second node which points to the first node and right there you're doomed because you have the same node in the list twice. This requirement doesn't make sense. — user4581301
– user4581301, Commented Apr 22, 2022 at 5:54

Reza · Accepted Answer · 2022-04-22 09:45:26Z

0

I have modified your code to show a correct answer:

#include <iostream>

struct ListNode
{
  int val;
  ListNode* next;
  ListNode(): val( 0 ), next( nullptr ) {}
  ListNode( int x ): val( x ), next( nullptr ) {}
  ListNode( int x, ListNode* next ): val( x ), next( next ) {}
};

void printlist( ListNode* head )
{
  while( head != nullptr ) {
    std::cout << head->val << " ";
    if( head->next )
      std::cout << "-> ";
    head = head->next;
  }
  std::cout << std::endl;
}

void reorderList( ListNode* head ) {
  ListNode* pf = head;
  ListNode* pt = nullptr;
  ListNode* tmp = nullptr;
  while( true )
  {
    // find n-1 node
    tmp = pf;
    while( tmp && tmp->next && tmp->next->next )
      tmp = tmp->next;
    // check to see n-1 node is not equal to the first node
    if( tmp == pf )
      break;
    // reorder
    pt = tmp;
    tmp = pf->next;
    pf->next = pt->next;
    pt->next->next = tmp;
    pf = tmp;
    pt->next = nullptr;
  }
}

int main( int argc, char** argv ) {
  ListNode* head = new ListNode( 1 ); 
  head->next = new ListNode( 2 );
  head->next->next = new ListNode( 3 );
  head->next->next->next = new ListNode( 4 );
  head->next->next->next->next = new ListNode( 5 );
  head->next->next->next->next->next = new ListNode( 6 );
  printlist( head ); // Print original list
  reorderList( head ); // Modify the list
  printlist( head ); // Print modified list

  return 0;
}

and the result is like below:

1 -> 2 -> 3 -> 4 -> 5 -> 6                                                                                              
1 -> 6 -> 2 -> 5 -> 3 -> 4

answered Apr 22, 2022 at 9:45

Reza

4,0895 gold badges40 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

HauresXI Over a year ago

for the while loop on the reorderList, what is being checked for true?

Reza Over a year ago

@HauresXI nothing! it's an infinite loop. I only check inside the loop that if the first and last node are equal then break the loop. BTW, don't forget to accept this answer :)

Kashem · Accepted Answer · 2022-04-22 11:20:34Z

There could be many solutions to your problem. I just modified your logic and added comments which could help you to understand. Happy link list coding.

#include <cstdlib>
#include <iostream>
    
using namespace std;

struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* newNode(int x){
    ListNode* temp = new ListNode;
    temp->val = x;
    temp->next = NULL;
    return temp;
}

void printlist(ListNode* head)
{
    while (head != NULL) {
        cout << head->val << " ";
        if (head->next)
            cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

void reorderList(ListNode* head){
    ListNode *curr = head;
    ListNode *temp=head;
    ListNode *last=NULL,*prev;
    while(curr->next != NULL){
        
        while(temp->next != NULL){
            //Prev variable is being used for remove last node connection from it previous node
            // For example 1->2->3
            // We need to remove 2->3 connection before adding 1->3
            // Otherwise it will create cycle i.e 1->3->2->3->2....
            prev = temp;
            temp=temp->next;
            last=temp;
            
        }
        // If node number is even this condition will check adding mid+1 node twice
        if(last==NULL) {
            break;
        }
        temp = curr->next;
        curr->next=last;
        last->next=temp;
        curr=curr->next->next;
        temp=curr->next;
        // Removing last node connection from it previous node
        prev->next = NULL;
        last = NULL;
    }
}

int main(int argc, char** argv) {
    ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
   //head->next->next->next->next->next = newNode(8);
 
    printlist(head); // Print original list
    reorderList(head); // Modify the list
    printlist(head); // Print modified list

    return 0;
}

Collectives™ on Stack Overflow

C++ reordering Singly Linked List

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related