{"id":27293,"date":"2018-01-20T20:46:48","date_gmt":"2018-01-20T15:16:48","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27293"},"modified":"2018-01-20T20:46:48","modified_gmt":"2018-01-20T15:16:48","slug":"java-algorithm-write-function-reverse-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-write-function-reverse-linked-list\/","title":{"rendered":"Java Algorithm – Write a function to reverse a linked list"},"content":{"rendered":"

Given pointer to the head node of a linked list, the task is to reverse the linked list.<\/p>\n

Examples<\/strong>:<\/p>\n

Input : Head of following linked list  \r\n       1->2->3->4->NULL\r\nOutput : Linked list should be changed to,\r\n       4->3->2->1->NULL\r\n\r\nInput : Head of following linked list  \r\n       1->2->3->4->5->NULL\r\nOutput : Linked list should be changed to,\r\n       5->4->3->2->1->NULL\r\n\r\nInput : NULL\r\nOutput : NULL\r\n\r\nInput  : 1->NULL\r\nOutput : 1->NULL<\/pre>\n
\n[ad type=”banner”]\n
Iterative Method<\/strong>
\nIterate trough the linked list. In loop, change next to prev, prev to current and current to next<\/p>\n
Java Programming:<\/strong><\/p>\n
 
 <\/div> 
#include<stdio.h>#include<stdlib.h> \/* Link list node *\/struct node{    int data;    struct node* next;}; \/* Function to reverse the linked list *\/static void reverse(struct node** head_ref){    struct node* prev   = NULL;    struct node* current = *head_ref;    struct node* next;    while (current != NULL)    {        next  = current->next;          current->next = prev;           prev = current;        current = next;    }    *head_ref = prev;} \/* Function to push a node *\/void push(struct node** head_ref, int new_data){    \/* allocate node *\/    struct node* new_node =            (struct node*) malloc(sizeof(struct node));                \/* put in the data  *\/    new_node->data  = new_data;                    \/* link the old list off the new node *\/    new_node->next = (*head_ref);                \/* move the head to point to the new node *\/    (*head_ref)    = new_node;} \/* Function to print linked list *\/void printList(struct node *head){    struct node *temp = head;    while(temp != NULL)    {        printf("%d  ", temp->data);            temp = temp->next;      }}     \/* Driver program to test above function*\/int main(){    \/* Start with the empty list *\/    struct node* head = NULL;        push(&head, 20);     push(&head, 4);     push(&head, 15);      push(&head, 85);                printf("Given linked list\\n");     printList(head);         reverse(&head);                           printf("\\nReversed Linked list \\n");     printList(head);         getchar();}<\/code><\/pre> <\/div>\n
Given linked list\r\n85 15 4 20 \r\nReversed Linked list \r\n20 4 15 85<\/pre>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
Recursive Method:<\/strong><\/p>\n
   1) Divide the list in two parts - first node and rest of the linked list.\r\n   2) Call reverse for the rest of the linked list.\r\n   3) Link rest to first.\r\n   4) Fix head pointer<\/pre>\n<\/div>\n
\"Write<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
void recursiveReverse(struct node** head_ref){    struct node* first;    struct node* rest;          \/* empty list *\/    if (*head_ref == NULL)       return;        \/* suppose first = {1, 2, 3}, rest = {2, 3} *\/    first = *head_ref;      rest  = first->next;     \/* List has only one node *\/    if (rest == NULL)       return;        \/* reverse the rest list and put the first element at the end *\/    recursiveReverse(&rest);    first->next->next  = first;           \/* tricky step -- see the diagram *\/    first->next  = NULL;               \/* fix the head pointer *\/    *head_ref = rest;              }<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(n)
\nSpace Complexity:<\/strong> O(1)<\/p>\n[ad type=”banner”]\n
Java Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ Java program for reversing the Linked list class LinkedList {     static Node head;     static class Node {         int data;        Node next;         Node(int d) {            data = d;            next = null;        }    }     \/\/ A simple and tail recursive function to reverse    \/\/ a linked list.  prev is passed as NULL initially.    Node reverseUtil(Node curr, Node prev) {         \/* If last node mark it head*\/        if (curr.next == null) {            head = curr;             \/* Update next to prev node *\/            curr.next = prev;            return null;        }         \/* Save curr->next node for recursive call *\/        Node next1 = curr.next;         \/* and update next ..*\/        curr.next = prev;         reverseUtil(next1, curr);        return head;    }     \/\/ prints content of double linked list    void printList(Node node) {        while (node != null) {            System.out.print(node.data + " ");            node = node.next;        }    }     public static void main(String[] args) {        LinkedList list = new LinkedList();        list.head = new Node(1);        list.head.next = new Node(2);        list.head.next.next = new Node(3);        list.head.next.next.next = new Node(4);        list.head.next.next.next.next = new Node(5);        list.head.next.next.next.next.next = new Node(6);        list.head.next.next.next.next.next.next = new Node(7);        list.head.next.next.next.next.next.next.next = new Node(8);         System.out.println("Original Linked list ");        list.printList(head);        Node res = list.reverseUtil(head, null);        System.out.println("");        System.out.println("");        System.out.println("Reversed linked list ");        list.printList(res);    }}  \/\/ This code has been contributed by Mayank Jaiswal<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/p>\n
Given linked list\r\n1 2 3 4 5 6 7 8\r\n\r\nReversed linked list\r\n8 7 6 5 4 3 2 1<\/pre>\n","protected":false},"excerpt":{"rendered":"
Java Algorithm – Write a function to reverse a linked list – Linked List – Given pointer to the head node of a linked list, the task is to reverse<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,2139,79476,79478],"tags":[80299,81347,81346,81349,80298,80296,81345,80300,81342,81348,80297,81344,81343],"class_list":["post-27293","post","type-post","status-publish","format-standard","hentry","category-coding","category-java","category-linked-list","category-singly-linked-list","tag-algorithm-to-reverse-a-linked-list-in-data-structure","tag-how-to-reverse-a-linked-list-c","tag-how-to-reverse-a-linked-list-in-c","tag-how-to-reverse-a-linked-list-python","tag-reverse-a-linked-list-algorithm","tag-reverse-a-linked-list-c","tag-reverse-a-linked-list-in-groups-of-size-k","tag-reverse-a-linked-list-recursively-c","tag-reverse-a-linked-list-using-recursion","tag-reverse-doubly-linked-list-java","tag-reverse-linked-list-recursive-java","tag-reversing-a-linked-list-in-c-with-explanation","tag-reversing-a-linked-list-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27293"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27293\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27293"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}