Reverse a Linked List Iterative Solution

In Iterative solution for reversing a Linked List  the core idea is as follows :

change link pointers :

next of current to previous
previous to current
current to next of current

Try imagining flow drawing 4 nodes and applying logic from code

Plus in the end  , since ours whole linked list links has been reversed and previous pointer points to last node of actual list given in start,
ours previous pointer holds the new head of reversed list


Node* Reverse(Node *head)
{
  if(head == NULL)
      return head;
   
  Node *prev = NULL  , *temp , *curr = head;
   
    while(curr != NULL)
        {
        temp = curr->next;
        curr->next = prev;
        prev  = curr;
        curr = temp;
    }
   
    head = prev;
    return head;
}

Linked List | Swapping Nodes without swapping data

Node* swapNode(Node* head  , int x  , int y )
{

    if(x == y)
        return ;
       
    Node* prevX = NULL  , *currX  = head, *currY = head , *prevY = NULL  ;
   
    //find xth and yth node
    for(int i = 0 ; i < x ; ++i)
    {
        prevX = currX ;
        currX = currX->next;
    }
    for(int i = 0 ; i < y ; ++i)
    {
        prevY = currY ;
        currY = currY->next;
    }
   
   
    if( currX == NULL || currY == NULL )
        reutrn;
       
       
    //doesnt matter x is smaller or bigger then y
   
        //change head ptr
    if(prevX != NULL )
        prevX -> next = currY;
    else
        head = currY;
       
    if(prevY != NULL )   
        prevY ->next = currX;
    else
        head = currX;
       
   
    //swap next pointers
    Node* temp = currX->next;
    currX->next = currY->next;
    currY->next = temp;
   
    return head;
   
}

LinkedList : Messing with head pointer

During my recent course of practice with LinkedList , i experienced many problems are related to keeping track of right Head pointer of the list . Whether its a Swapping Nodes without swapping data or simple insertion and deletion of nodes.

Pointer :  When dealing with Swapping Nodes , Insertion and Deletion at head , if the pointer to previous Node is NULL  , then it means First Node is  under consideration


This is how I approach :

Node* prevNode = NULL ; 
Node* ptr = head;

for(int i = 0 ; i < position ; ++ i
{
      prevNode = ptr;
      ptr = ptr->next;
}


if( prevNode == NULL )
{
     //  manipulate head pointer here
}

Checkout Swapping Nodes without swapping data for a real life problem

Stack with Linked List

//STACK WITH linked list

#include<stdlib.h>
#include<limits.h>
#include<conio.h>
#include<stdio.h>

struct StackNode {
    int data;
    struct StackNode* next;
};

struct StackNode* newNode(int data)
{
    struct StackNode* node = (struct StackNode*) malloc(sizeof(struct StackNode));
    node->data = data;
    return node;

}

int isEmpty(struct StackNode* root)
{
    return !root;
}

void push(struct StackNode** root, int item)
{
    struct StackNode* node = newNode(item);
    node->next = *root;

    *root = node;
    printf("pushed %d \n", item);

}

void pop(struct StackNode** root)
{
    if (isEmpty(*root))
    {
        printf("Underflow \n");
        return;
    }
    int poped = (*root)->data;
    struct StackNode* temp = *root;
    *root = (*root)->next;
    free(temp);

    printf("popped %d\n", poped);

}

void peek(struct StackNode* root)
{
    if (isEmpty(root))
    {
        printf("empty stack \n");
        return;
    }
    printf("peeked %d \n" , root->data);

}


int main()
{
    struct StackNode* stackRoot = NULL;
    push(&stackRoot, 4);
    push(&stackRoot, 6);

    pop(&stackRoot);

    peek(stackRoot);

    pop(&stackRoot);
    peek(stackRoot);
    push(&stackRoot, 6);
    peek(stackRoot);

    getchar();
    return 0;


}

Check if two linked lists are identical

int isIdentical(struct node* a , struct node* b )
{
    if(a == NULL && b == NULL)
    {
        return 1 ;
    }
    if(a == NULL && b != NULL)
    {
        return 0 ;
    }
    if(a != NULL && b == NULL)
    {
        return 0 ;
    }
    if(a->data !=  b-> data)
    {
        return 0 ;
    }
   
    return isIdentical(a->next ,  b->next );
   

}

Merge two sorted linked list in a sorted order

//merge two sorted linked list in sorted order

void MoveNode(struct node **dest , struct node **src)
{
    struct node* newNode = *src;
   
    assert(newNode != NULL) ;
   
    //advance src
    *src = newNode->next;
   
    //link new node with destination old reference
    newNode->next = *dest;
   
    //point dest to new node
    *dest = newNode;
   

}


struct  node*  merge(struct node** a , struct node** b )
{
    struct node dummy;
   
   
    //pointer to tail for easy appendinng at end of list in MoveNode()
    struct node* tail = &dummy;
   
    dummy->next = NULL;
   
    while(1)
    {
        if( a == NULL)
        {
            tail->next = b ;
            break;
        }
        else if( b == NULL)
        {
            tail->next = a ;
            break;
        }
        else if (a->data <= b->data)
        {
            MoveNode(&(tail->next) , &a);
        }
        else
        {
            MoveNode(&(tail->next) , &a);
        }
        tail = tail->next;
    }
   
    return ( dummy -> next);
}

Reverse a linkes list

struct node {
    int data ;
    struct node* next ;
}

// use pointer to node because we gotta change head reference value in function

void reverseList(node** head)
{
    struct node* current = *head;
    struct node* prev = NULL;
    struct node* next ;
   
   
    while( current != NULL)
    {
        //save next node
        next = current->next;
       
        //shift previous node , reversing two nodes at a time (current and previous)
        current->next = prev ;
        //update prev
        prev = current ;
       
        //update current pointing rest of the list
        current = next ;
       
    }
   
    //update head
    *head = prev ;
}


Simple Visualisation  inside loop

Sample linked list

1 -> 2 -> 3
Iterations :
1 :     1-> NULL (*prev == 1 )  , 2->3 (*current == 2)
2 :     2->1->NULL (*prev == 2) , 3-> NULL
3:     3->2->1-> (*prev == 3)  , NULL

Loop over  ,  update  *head = prev
       

Remove duplicates in a sorted linked list

 Complexity O(n)

struct Node {
    int data ;
    struct Node * next ;
};

 

typedef struct Node * Node ;



void removeDuplicate (Node * head){
    if( head == NULL)
        return ;
    Node next_next = head->next ;
   
    while ( head -> next != NULL)
    {
        if( head->data == head->next->data)
        {
            //remove the next  duplicate node
            head->next = next_next->next;
            free(next_next);
            next_next = head->next ;
           
        }
        //advance only if no deletion occurs , because on deleting a node , we have no info about equality of the current and next (next_next) node
        else {
            head = head->next ;
        }
    }
}

Given 3 linked list , find a triplet such that there's sum equals a given number

    A function to check if there exist a triplet in three given linked list such that the tripplet's sum is equal to a given number
    Let there be 3 linked list a , b , c .
   
    1 Sort list b in ascendinng and c and descending order respectively

    2 For each node in  list a ,check if there exist a triplet traversing list b and c as shown in function below.

    The technique is called Quadratic algorithm for 3 sum problem

    Function assumes list b and c already satisfies 1st step and all list are of same length

#include<iostream>
using namespace std;
struct node {
    int data;
    struct node * next;


};

bool isTripletPresent(struct node* aHead, struct node* bHead,  struct node* cHead, int num)
{
    struct node* a = aHead;
    while (a != NULL)
    {
        struct node* b = bHead;
        struct node* c = cHead;

        while (b != NULL  && c != NULL)
        {
            int sum = a->data + b->data + c->data;
            if (sum == num)
            {
                cout << "Found";
                return true;
            }
            else if (sum < num)
            {
                //look for greater value in b
                b = b->next;
            }
            else {
                //look for smaller value in c
                c = c->next;
            }


                       
        }

        a = a->next;



    }
    cout << "No such triplet ";
    return false;
}

C programme to check if a linked list is circular

// c program to check if a linked list is circular

struct Node {
    int data ;
    struct Node* next ;

};

typedef Node* Node ;

int isCircularLinkedList(Node head)
{
     Node slowPtr = fastPtr = head ;
    
     while (slowPtr && fastPtr )
     {
        slowPtr = slowPtr->next ;
        fastPtr = fastPtr -> next;
       
        if( ! fastPtr )
        {
            return 0 ;
        }
        else {
            fastPtr = fastPtr - > next ;
        }
       
        if( slowPtr = fastPtr )
            return 1 ;
       
     }
    
     return 0 ;
}

C : find middle element using two pointer technique

// c code to find middle element using two pointer technique

struct Node {
    int data ;
    struct Node* next ;

};

typedef Node* Node ;

Node middleNodeOfLinkedList(Node head)
{
    Node slowPtr = fastPtr = head ;
   
    if(head->next != NULL )
    {
        fastPtr = fastPtr->next->next;
    }
   
    while (fastPtr != NULL )
    {
        // check for more nodes  at the node pointed by  fastPtr
        if(fastPtr -> next != NULL)
        {
            //advance fastPtr
            fastPtr = fastPtr->next->next ;
        }
        else {
            return slowPtr;
        }
       
        //advance slow ptr
        slowPtr = slowPtr->next ;
       
   }
  
   return slowPtr;
  
  
}

Deleting a node in a linked list when only a reference to only that very node is given

public static boolean delNode(LinkedlIstNode n )
{
    if ( n  ==  null || n.next == null )
    {
         //invalid linked list node
        return false ;
    }
    else
    {
        n = n.next.data ;
        n = n.next ;
        return true ;
    }   
}


A situation arises if given node n is last node . We can set last  node as a sentinal  of a dummy node.

Find kth to the last ellement in a linked list

kth to the last element would be at [length-k] element , if the length of a linked list.
But since length is not known, we can either use iteration or recursion.

For recursion -
To simply print the kth to the least element in singly linked list , use a counter variable which increments itself
when each time the return statement is executed during recursion.
When counter equals "k" , print the value of node at that instance .
Recursion mostly imploys counter manipulation -

public static int nthToTheLast( LinkedListNode head , int k  )
{
    //base case
    if ( head == null )
        return 0 ;
   
    //recur to reach end of the list
    int counter = nthToTheLast(  head.next , int k  ) + 1 ;
    if( counter == k )
        System.out.println(head.data);
    return counter ;
   

}

However if the question demands to return a kth to the last "node" , since we can only return a single Object at one time, an object of
a suitable wrapper class having integer value of the counter saved can be passed on each instance of recursion as in JAVA  we dont have
pointers to pass by reference , but a wrapper class can help to mimic it -
For JAVA -

public class IntWrapper()
{
    public int val = 0 ;
}

public LinkListNode nthToTheLast(LinkListNode head , int  k , IntWrapper counter)
{
    //base case
    if( head == null) return 0 ;
   
    LinkListNode =  nthToTheLast(LinkListNode head , int  k , IntWrapper counter) ;
    if ( ++counter.val == k )
        return head ; // we have found ours kth element

    return node ;

}



Also, using C++ feature of pass by reference , an allias of the counter can be manipulated without using wrapper class -

node* nthToTheLast( Node* head , int  k , int& counter)
{
    if( head == NULL) return NULL ; //base case
   
    node&* result = nthToTheLast( Node* head , int  k , int& counter);
    if(++counter == k )
        return head;
    return result;
}


All recursive algos for this case are O(n) for both space and time but clean .
For O(1) space complexity , the runnining technique , using 2 pointers for linked list can be used as follows -

 public static LinkListNode nthToTheLastNode( LinkListNode head ,  int  k  )
 {
    LinkListNode p1 = p2 = head ;
   
    //iterate p2 n position from start , such that difference between positions of p2 and p1 is k
    for( int  i = 0 ; i < k - 1 ; ++i)
    {
        if( p2 == null ) return null ; // list is too small
            p2 = p2.next ;
    }
   
    if (p2 == null ) return  null ; // Error check : list is small
       
    //now move p1 and p2 with same pace ,  till p2 reaches end of the list.
    // at this instance , p1 will be at kth to the last node
    while ( p2.next != null )
    {
            p2 = p2.next ;
            p1 = p1.next ;
    }
   
    return p1 ;
   
   
 }

Remove Duplicates from a linked lisr

With a HashSet as buffer = Time = O(n), space = O(n)
Using two pointer technique - running method -  Time = O(n^2) Space = O(1)

// with HashSet as buffer
public static removeDuplicates(LinkedListNode head)
{
    HashSet<Integer>set =  new HashSet<Integer>();
    LinkedList ptr = head, prev = null;
    while(ptr != null )
    {
   
        if(set.contains(ptr.data))
        {
            prev.next = ptr.next;
        }
        else
        {
            set.add(ptr.data);
            prev = ptr;
        }
        ptr = ptr.next;
    }
}


//using 2-point pointer running technique

public static removeDuplicates(LinkedListNode head)
{
    LinkedList p1 = head;
    LinkedList p2 = p1.next ;
    LinkedList prev = null
    while( p1.next != null )
    {
        while( p2 != null )
        {
            if( p2.data == p1.data )
            {
                prev.next  = p2.data;
            }
            else
            {
                prev = p2;
            }
            p2  = p2.next;
           
        }
    }
}

Doubly Linked List using c++

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include<string>

struct _node_student;

#define CREATE_NODE  ( struct _node_student* ) malloc(sizeof(_node_student) )

using namespace std;

// a struct to represent a student in a queue as a node of a doubly linked list
struct _node_student{
    //the student number
    unsigned int _std_num = 0;
    //pointer to next student node
    _node_student* next;
    //pointer to previous student node
    _node_student* prev;

} *ptr;


//class implementing a doubly linked list for queue at the department


class Queue{
    //total students PROCESSED  in queue at any instance 
    unsigned int _ttl_stdnt_procsd;

    //pointer to front of the queue
    _node_student* front;
    //pointer to end of the queue
    _node_student* end;

public:

    //constructor
    Queue(){
        _ttl_stdnt_procsd = 0;

        //make fornt and end point eachother
        front = CREATE_NODE;
        end = CREATE_NODE;

        front->next = NULL;
        front->prev = NULL;

        end->prev = front;
        end->next = NULL;

        front->next = end;
    }

    //accessor and manipulation functions
    void  addAtHead(unsigned int _ttl_stud);
    void  addAfter(unsigned int _stud_num);
    void  addBefore(unsigned int _stud_num);
    void  removeStudent(unsigned int num);
    void display();

    //getter and setter for total student processed
    int getTtlStdProcsd(){ return _ttl_stdnt_procsd; };
    void incrmntTtlStdProcsd(){ ++_ttl_stdnt_procsd; };


};


//functions add students at the end of queue
void Queue::addAtHead(unsigned int _ttl_stud)
{
    //get the  student number of first student  to be added this time as index
    unsigned int  index = getTtlStdProcsd() + 1;

    // update total student
    _ttl_stud += getTtlStdProcsd();

    //add all students at at end of the queue
    while (index <= _ttl_stud)
    {


        //get  end  student node already in queue
        _node_student* u = CREATE_NODE;
        u = end->prev;


        //create a new student node and initialise its number
        _node_student* v = CREATE_NODE;

        //update the queue by adding student node v after u in the queue
        v->next = end;
        v->prev = u;
        v->_std_num = index;


        u->next = v;
        end->prev = v;


        ++index;

        //increment total student processed
        incrmntTtlStdProcsd();
    }


}



// test function to display the queue

void Queue::display()
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->next != NULL)
    {
        cout << ptr->_std_num << " ";
        ptr = ptr->next;
    }



}


// add a student node before his/her's best  friend ;)
void Queue::addBefore(unsigned int _stud_num) {

    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* u = CREATE_NODE;


    u = ptr->prev;

    //add v before his friend _stud_num
    v->next = ptr;
    v->prev = ptr->prev;

    ptr->prev = v;
    u->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();



}


// add a student node after his/her's best  friend :P
void Queue::addAfter(unsigned int _stud_num)
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* w = CREATE_NODE;

    w = ptr->next;

    //add v after student _stud_num
    v->next = ptr->next;
    v->prev = ptr;

    w->prev = v;
    ptr->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();


}


// kick out students from the queue
void Queue::removeStudent(unsigned int _stud_num)
{


    for (unsigned int i = 0; i < _stud_num; ++i)
    {
        _node_student* tmp = front;
        front = front->next;
        free(tmp);

    }


}

Java - Stack using Linked List

/*
 * Implements a generic type of node to implement a generic stack  - see  here - using a generic linked list
 */

public class Node<E> {
// instance variables
private E element;
private Node<E> next;

// create a node with null references
public Node() {
this(null, null);
}
   //create a node with the given elemment and next node
public Node(E e , Node<E> n){
element = e;
next = n ;
}

//accessor methods
public E getElement(){
return element;
}
public Node<E> getNext(){
return next;
}

//modifier methods 
public void setElement(E newElem){
this.element =  newElem ;
}

public void setNext(Node<E> newNext){
next = newNext;
}
}





/*
 * Implements the Stack interface  - see  here - using a singly linked list , whose nodes are objects of class Node 
 * All mehtods of Stack interface are executed in constant time 
 * Space requirement - O(n)
 * New exception  creation for overflow problem is not required , unlike arrays based stack 
 * 
 */

import java.util.EmptyStackException;
public class NodeStack<E> implements Stack<E> {
protected Node<E> top;// reference to head
protected int size;

// construct an empty stack
public NodeStack() {
top = null;
size = 0;
}

@Override
public int size() {
return size;
}

@Override
public boolean isEmpty() {
if (top == null)
return true;
return false;
}

@Override
public E top() throws EmptyStackException {
if(isEmpty()) throw new EmptyStackException();
return top.getElement();
}

@Override
public void push(E element) {
Node<E> v = new Node<>(element, top); // create and link in a new node
top = v;
++size;
}



@Override
public E pop() {
if(isEmpty()) throw new EmptyStackException();
E temp =  top.getElement();
top = top.getNext(); //  link out former top node 
--size;
return temp ; 
}


}

Recursion on Linked List

Recursion allows us flexibility in printing out a list forwards or in reverse (by exchanging the order of the recursive call)
Recursion takes away looping and checking for special cases using dummy head or tails nodes , if you dont  believe me , try writing an iterating for or while loop recursive algos !

The classes required for Node and SinglyLinkedList object are  implemented here  - see -

Following function using recursion should be added to SinglyLinkedList class for implementation - 

Printing the elements of list - 


// Recursively prints the output of list
public void printList(Node n) {

if(n  == null)
{
return;
}

/*
*  to print in reverse order  just exchange the following statements ! ---
*  printList(n.getNext());
* if(n != null)
* System.out.println(n.getElement());
*/
if(n != null)
System.out.println(n.getElement());
printList(n.getNext());

}
}

Call -
SinglyLinkedList  sll =  new SinglyLinkedList();
sll.printList(sll.head);


Length of a linked list - 
public int length(Node n) {
if(n == null)
return  0;
else
return 1 + length(n.getNext());
}


//example call 
System.out.println(sll.length(sll.head));

Paradigm -  reconstruct the list

It is helpfull if we see insertion and deletion operations on linked list in terms of reconstruction  . Now u may say that  i have gone nuts because  i implemented  inserting a  node at head and tail in SinglyLinkedList class  without reconstrcution unlike as it is usually  an element is inserted in arrays . That is insane because this approach completely overwrites the dynamic nature of linked list.

But check out this silly function of reconstrcution ahead  which makes you trivially reconstruct all nodes of linked list by reassighning references to all nodes-

public Node reconstruct(Node p)
{
if(p ==  null)
{
return null;
}

               //silly part
p.setNext(reconstruct(p.getNext()));
return p;

}


}

Now what you do is exploit this reconstruct's silly part to do  anything you wish to do with the node reassgihned , suppose concate a "1" to every string - 

public Node concateOne(Node p)

{

if(p ==  null)

{

return null;

}

                

                // Silly really ? 

p.setElement(p.getElement().concat("1")) ;

p.setNext(concateOne(p.getNext()));

return p;

}

// example call

sll.head = sll.concateOne(sll.head);

sll.printList(sll.head);

Some more so called silly traversing based linked list function based on recursion - 

Copying a linked list -
// create copy of existing 
public Node copy(Node n) {
if(n ==  null)
return null ;
else
return new Node(n.getElement() ,copy(n.getNext()));
}

Example call


// add the new copy to newly created singly linked list
SinglyLinkedList newList = new  SinglyLinkedList();
                //create a copy
newList.head =  sll.copy(sll.head);
//print the new list

newList.printList(newList.head);

Let me repeat again for you that  we need NOT use any dummy header and check for special case of empty list or inserting at head leading to IllegalStateException or IllegalArgumentException , when using this recursive paradigm of  "reconstruct " .

Yup , i know , silly enough to grasp :P 

Singly Linked List - java

Base classes for singly linked list - the head and tail are sentinels for the singly linked list  list



Node class
/*
 *  @ Node class to implement a node of a linked list
 *  @data Element the string data of node , Next the reference to the next node object reference
 */
public class Node {
private String element ;
Node next ;

//constructor
//creates a node with given element and reference to the next node
public Node(String s , Node n)
{
this.element = s;
this.next = n;

}

// getters and setters modifiers for this node
public String getElement()
{
return this.element;
}

public Node getNext()
{
return this.next;
}

public void setElement( String newElem )
{
this.element = newElem;
}
public void setNext( Node newNxt )
{
this.next = newNxt;
}

}


Singly Linked List class - 

/*

 *  @ SinglyLinkedList class to implement singly linked list

 */

public class SinglyLinkedList {

//head and tail of list

protected Node head , tail  ;

static int totalNodes ; 

//default constructor creates an empty list

public SinglyLinkedList()

{

this.head = null;

SinglyLinkedList.totalNodes = 0 ;

}

// insertion at the head of a linked list

public void addAtHead(Node newNode)

{

//set the next reference of new node same as head of the linked list

newNode.setNext(head);

//make head to  point the new node making new node to be the first element of the linked list

head = newNode ; 

// increment the number of nodes  

++totalNodes;

}

//insert at the tail of linked list

public void addAtTail(Node newNode)

{

//set the next referencee of new node ass null 

newNode.setNext(null);

//make the last node to point the newNode

tail.setNext(newNode);

// now finally make the tail to point to the newNode

tail = newNode ; 

// increment the total nodes present

++totalNodes;

}

// remove the first element of the list

public void removeFirstNode(){

// store the first node in a  temporary reference to remove it

Node temp = head ; 

// make head to point to the second node 

head =  head.getNext();

// null out the next poiner of the removed node

temp.setNext(null);

//decrement the total nodes present

--totalNodes;

}

}