js

Saturday, August 27, 2022

206. Reverse Linked List

 

Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Examples: 

Input: Head of following linked list 
1->2->3->4->NULL 
Output: Linked list should be changed to, 
4->3->2->1->NULL

Input: Head of following linked list 
1->2->3->4->5->NULL 
Output: Linked list should be changed to, 
5->4->3->2->1->NULL

Input: NULL 
Output: NULL

Input: 1->NULL 
Output: 1->NULL 
 


Iterative Method 

  1. Initialize three pointers prev as NULL, curr as head and next as NULL.
  2. Iterate through the linked list. In loop, do following. 
    // Before changing next of current, 
    // store next node 
    next = curr->next
    // Now change next of current 
    // This is where actual reversing happens 
    curr->next = prev 
    // Move prev and curr one step forward 
    prev = curr 
    curr = next

Below is the implementation of the above approach: 

Output: 

Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85

Time Complexity: O(n) 
Auxiliary Space: O(1)

Recursive Method: 

   1) Divide the list in two parts - first node and 
      rest of the linked list.
   2) Call reverse for the rest of the linked list.
   3) Link rest to first.
   4) Fix head pointer

Linked List Rverse

// Recursive C++ program to reverse
// a linked list
#include <iostream>
using namespace std;
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
struct LinkedList {
    Node* head;
    LinkedList()
    {
        head = NULL;
    }
 
    Node* reverse(Node* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
 
        /* reverse the rest list and put
          the first element at the end */
        Node* rest = reverse(head->next);
        head->next->next = head;
 
        /* tricky step -- see the diagram */
        head->next = NULL;
 
        /* fix the head pointer */
        return rest;
    }
 
    /* Function to print linked list */
    void print()
    {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
 
    void push(int data)
    {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
 
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    LinkedList ll;
    ll.push(20);
    ll.push(4);
    ll.push(15);
    ll.push(85);
 
    cout << "Given linked list\n";
    ll.print();
 
    ll.head = ll.reverse(ll.head);
 
    cout << "\nReversed Linked list \n";
    ll.print();
    return 0;
}

Output: 

Given linked list
85 15 4 20 
Reversed Linked list
20 4 15 85

Time Complexity: O(n) 
Auxiliary Space: O(n)

A Simpler and Tail Recursive Method 

Below is the implementation of this method.  

 
 

Output
Given linked list
1 2 3 4 5 6 7 8 

Reversed linked list
8 7 6 5 4 3 2 1

Time Complexity: O(N)

As we do certain operation for every node of the linked list.

Auxiliary Space: O(1)

As constant extra space is used.

Head Recursive Method:

// Head recursive C++ program to reverse a linked list
#include <iostream>
using namespace std;
 
// Linked list node
class Node {
public:
    int data;
    Node* next;
 
    // constructor: automatically assigns the value to the
    // data and next pointer to NULL
    Node(){};
    Node(int val)
        : data(val)
        , next(NULL){};
};
 
void reverseUtil(Node* curr, Node* prev, Node** headref)
{
    // Base Case - If curr is last node
    if (curr->next == NULL) {
        // Update head of the linked list
        *headref = curr;
        // Update next to prev node
        curr->next = prev;
        return;
    }
    // Recursive Call for next node
    reverseUtil(curr->next, curr, headref);
    // Update next to prev node
    curr->next = prev;
}
 
void reverse(Node** headref)
{
    // If linked list is empty or contains single node
    if (*headref == NULL || (*headref)->next == NULL)
        return;
    // Call reverseUtil() with prev as NULL
    reverseUtil(*headref, NULL, headref);
}
 
// Function to insert a node at the end of linked list
void push(Node** headref, int x)
{
    Node* newptr = new Node(x);
    if (*headref == NULL) {
        *headref = newptr;
    }
    else {
        Node* temp = *headref;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newptr;
    }
}
 
// Functio to print the linked list
void print(Node* headref)
{
    while (headref != NULL) {
        cout << headref->data << " ";
        headref = headref->next;
    }
    cout << "\n";
}
 
int main()
{
    Node* head = NULL;
 
    // head->1->2->3->4->5->6->NULL
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 4);
    push(&head, 5);
    push(&head, 6);
 
    cout << "Given Linked List\n";
    print(head);
 
    reverse(&head);
    cout << "Reversed Linked List\n";
    print(head);
    return 0;
}
 
//This code is contributed by Anisha Wagh

Output:

Given Linked List
1 2 3 4 5 6

Reversed Linked List
6 5 4 3 2 1

Time Complexity : O(N)

Auxiliary Space: O(N) for call stack

Using Stack:

Algorithm – 

  • Store the nodes(values and address) in the stack until all the values are entered.
  • Once all entries are done, Update the Head pointer to the last location(i.e the last value).
  • Start popping the nodes(value and address) and store them in the same order until the stack is empty.
  • Update the next pointer of last Node in the stack by NULL.

Below is the implementation of the above approach:

// C++ program for above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Create a class Node to enter values and address in the list
class Node {
public:
    int data;
    Node* next;
};
 
// Function to reverse the linked list
void reverseLL(Node** head)
{
    // Create a stack "s" of Node type
    stack<Node*> s;
    Node* temp = *head;
    while (temp->next != NULL) {
        // Push all the nodes in to stack
        s.push(temp);
        temp = temp->next;
    }
    *head = temp;
    while (!s.empty()) {
        // Store the top value of stack in list
        temp->next = s.top();
        // Pop the value from stack
        s.pop();
        // update the next pointer in the list
        temp = temp->next;
    }
    temp->next = NULL;
}
 
// Function to Display the elements in List
void printlist(Node* temp)
{
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}
 
// Program to insert back of the linked list
void insert_back(Node** head, int value)
{
 
    // we have used insertion at back method to enter values
    // in the list.(eg: head->1->2->3->4->Null)
    Node* temp = new Node();
    temp->data = value;
    temp->next = NULL;
 
    // If *head equals to NULL
    if (*head == NULL) {
        *head = temp;
        return;
    }
    else {
        Node* last_node = *head;
        while (last_node->next != NULL)
            last_node = last_node->next;
        last_node->next = temp;
        return;
    }
}
 
// Driver Code
int main()
{
    Node* head = NULL;
    insert_back(&head, 1);
    insert_back(&head, 2);
    insert_back(&head, 3);
    insert_back(&head, 4);
    cout << "Given linked list\n";
    printlist(head);
    reverseLL(&head);
    cout << "\nReversed linked list\n";
    printlist(head);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)
Output
Given linked list
1 2 3 4 
Reversed linked list
4 3 2 1 

Thanks to Gaurav Ahirwar for suggesting this solution. 

Time Complexity: O(N)

As we do certain operation for every node of the linked list.

Auxiliary Space: O(N)

Space is used to store the nodes in the stack.

Using array:

Algorithm :- 

1. Create a linked list.

2. Count the number of nodes present in the Linked List

3. Initialize an array with the size of the count.

4. Store the elements of the Linked list in array 

5. Print the array from the last index to the first.

Input :  1->2->3->4->5
Output: 5->4->3->2->1

Time complexity: O(N) as we visit every node once.

Auxiliary Space: O(N) as extra space is used to store all the nodes in the array.

No comments:

Post a Comment

  Write a Program to Find the Maximum Depth or Height of a Tree Difficulty Level : Easy Last Updated : 21 Jul, 2022 Read Discuss Given ...