Java : Reversing a singly linkedlist in linear time

Program: Reverse a singlylinked List

complexity : O(n)

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class SinglyLinkedListNode {
    private int value;
    private int next;

    public SinglyLinkedListNode(int v){
        this.value = v;
        this.next = -1;
    }

    public int getValue(){
        return this.value;
    }

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

    public void setNext(int n){
        this.next = n;
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class ReverseSinglyLinkedList {
    private static int[] input = new int[]{0,1,2,3,4,5,6,7};
    private static SinglyLinkedListNode[] nodes = new SinglyLinkedListNode[input.length];
    private static int head = -1;
    private static int tail = -1;

    public static void main(String args[]){
        createList();
        printList(head);
        printList(reverseList(head));

    }

    private static void createList(){
        for(int i=0; i<input.length; i++){
            SinglyLinkedListNode node = new SinglyLinkedListNode(input[i]);
            nodes[i] = node;
            if(i==0){
                head = i;
                tail = i;
                continue;
            }
            /* setting parent's next*/
            nodes[i-1].setNext(i);
            tail = i;
        }
    }

    private static int reverseList(int head){
        SinglyLinkedListNode next = null;
        SinglyLinkedListNode current = null;
        int result = -1;

        current = nodes[head];
        while(current != null){
            if(current.getNext() == -1){
                current.setNext(result);
                result = current.getValue();
                break;
            }
            next = nodes[current.getNext()];
            current.setNext(result);
            result = current.getValue();

            current = next;
        }
        return result;
    }

    private static void printList(int head){
        while(head != -1){
            System.out.print(nodes[head].getValue() + " ");
            head = nodes[head].getNext();
        }
        System.out.println("");

    }
}

Output:

run:
0 1 2 3 4 5 6 7 
7 6 5 4 3 2 1 0 
BUILD SUCCESSFUL (total time: 0 seconds)

Java : reversing a doubly linkedlist on linear time

Complexity: O(N)

Program:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class DoublyLinkedListNode {
    private int value;
    private DoublyLinkedListNode previous;
    private DoublyLinkedListNode next;

    public DoublyLinkedListNode(int v){
        this.value = v;
        this.previous = null;
        this.next = null;
    }

    public void setPrevious(DoublyLinkedListNode prev){
        this.previous = prev;
    }

    public void setNext(DoublyLinkedListNode n){
        this.next = n;
    }

    public int getValue(){
        return this.value;
    }

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

    public DoublyLinkedListNode getPrevious(){
        return this.previous;
    }
}

 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package careercup.google;

/**
 *
 * @author Harit
 */
public class ReverseDLinkedList {

    private static DoublyLinkedListNode tail = null;
    private static DoublyLinkedListNode head = null;
    public static void main(String args[]){
        for(int i=0; i < 10; i++){
            DoublyLinkedListNode node = new DoublyLinkedListNode(i);
            if(head == null){
                head = node;
                tail = node;
            }
            if(i != 0){
                tail.setNext(node);
                node.setPrevious(tail);
                tail = node;
            }
        }
        printList(head);

        System.out.println("");
        System.out.println("Reversing the list");

        printList(reverseList(head));
    }

    private static DoublyLinkedListNode reverseList(DoublyLinkedListNode head){
        DoublyLinkedListNode start = head;
        DoublyLinkedListNode temp = null;

        while(head != null){
            temp = head.getNext();
            head.setNext(head.getPrevious());
            head.setPrevious(temp);

            if(head.getPrevious() == null){
                head.setPrevious(start);
                break;
            }
            head = head.getPrevious();
        }
        return head;
    }

    private static void printList(DoublyLinkedListNode head){
        System.out.print("List : ");
        while(head != null){
            System.out.print(head.getValue() + " ");
            head = head.getNext();
        }
    }
}

Output:
run:
List : 0 1 2 3 4 5 6 7 8 9
Reversing the list
List : 9 8 7 6 5 4 3 2 1 0
BUILD SUCCESSFUL (total time: 0 seconds)
                    

Build linkedlist at tail/end – C

There are two approaches given in the solution – using addNode() and addNodeWithDummy()

#include<stdio.h>

struct node* addNode();

struct node* addNodeWithDummy();

struct node* Push(struct node**, int);

struct node{

int data;

struct node* next;

};

main(){

struct node* head = NULL;

head = malloc(sizeof(struct node));

head = addNode();

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

head = addNodeWithDummy();

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

}

struct node* addNode(){

struct node* head = NULL;

struct node* tail = NULL;

int i;

head = malloc(sizeof(struct node));

tail = malloc(sizeof(struct node));

/* dealing with head node here */

Push(&head,1);

tail = head;

/*dealing with all other nodes using ‘tail’ */

for(i=2; i<6; i++){

Push(&(tail->next),i);

tail = tail->next;

}

tail->next = NULL;

return head;

}

struct node* addNodeWithDummy(){

struct node dummy;

struct node* tail = &dummy;

int i;

dummy.next = NULL;

for(i = 6; i <11; i++){

Push(&(tail->next),i);

tail = tail->next;

}

tail->next = NULL;

return (dummy.next);

}

struct node* Push(struct node** elem, int data){

struct node* current = NULL;

current = malloc(sizeof(struct node));

current->data = data;

current->next = *elem;

*elem = current;

return *elem;

}

output :

1 2 3 4 5

6 7 8 9 10

Appending nodes in linkedlist – C program

#include<stdio.h>

struct node{

int data;

struct node* next;

};

void appendNode(struct node** headRef, int data){

struct node* current = *headRef;

struct node* newNode = NULL;

newNode = malloc(sizeof(struct node));

newNode->data = data;

newNode->next = NULL;

if(current == NULL){

*headRef = newNode;

}else{

while(current->next != NULL){

current = current->next;

}

current->next = newNode;

}

}

main(){

struct node* head = NULL;

//head = malloc(sizeof(struct node));

appendNode(&head,1);

appendNode(&head,2);

appendNode(&head,3);

appendNode(&head,4);

appendNode(&head,5);

while(head != NULL){

printf(“%d “,head->data);

head = head->next;

}

printf(“\n”);

}

output : 1 2 3 4 5