链表Linked List-Reverse a Linked List反转链表的4种方法（3）

分手后的思念是犯贱 2023-09-24 19:24 56阅读 0赞

# Question #

> 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

# Methods #

## 1）Reverse a linked list by Iterative Method ##

The idea is to **use three pointers** `curr`, `prev`, and `next`to keep track of nodes to update reverse links.

**Time Complexity**: `O(N)`, Traversing over the linked list of size N.  
**Auxiliary Space**: `O(1)`  
![在这里插入图片描述][7136ecc0cb8612a1a253c24155074c23.gif_pic_center]  
![在这里插入图片描述][dfe99044abe94b1a83c724d48aaeebde.png]

### Steps: ###

*  Initialize three pointers `prev as NULL`, `curr as head`, and `next as NULL`.
 *  Iterate through the linked list. In a loop, do the following:
    
     *  Before changing the next of curr, store the next node
        
         *  next = curr -> next
     *  Now update the next pointer of curr to the prev
        
         *  curr -> next = prev
     *  Update prev as curr and curr as next
        
         *  prev = curr
         *  curr = next

package com.amy;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d) {
        
                val = d;
                next = null;
            }
        }
    
    
        // helper function: reverse a list
        ListNode reverse(ListNode node) {
        
            ListNode prev = null, curr = node, next = null;
    
            while (curr != null) {
        
                next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            node = prev;
            return node;
        }
    
    
        static void printList(ListNode node) {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.next;
            }
        }
    
    
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(2);
            list.head.next.next = new ListNode(3);
            list.head.next.next.next = new ListNode(4);
            list.head.next.next.next.next = new ListNode(5);
            list.head.next.next.next.next.next = new ListNode(6);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
            head=list.reverse(head);
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
    
        }
    }

Linked List before : 
    1 2 3 4 5 6 
    
    Linked List after: 
    6 5 4 3 2 1

## 2)Reverse a linked list using Recursion: ##

The idea is to reach the last node of the linked list `using recursion` then start reversing the linked list.

`Time Complexity`: `O(N)`, Visiting over every node one time  
`Auxiliary Space`: `O(N)`, Function call stack space  
![在这里插入图片描述][e147394cc9684103b6ddfc4eb21abb73.png]

### Steps ###

Follow the steps below to solve the problem:

*  Divide the list in two parts – first node and rest of the linked list.
 *  Call reverse for the rest of the linked list.
 *  Link the rest linked list to first.
 *  Fix head pointer to NULL

package com.amy;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d) {
        
                val = d;
                next = null;
            }
        }
        
        ListNode reverse(ListNode node) {
        
            if(node ==null||node.next ==null) return node;
            ListNode rest = reverse(node.next);
            node.next.next=node;
            node.next =null;
            return rest;
        }
    
    
        static void printList(ListNode node) {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.next;
            }
        }
    
    
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(2);
            list.head.next.next = new ListNode(3);
            list.head.next.next.next = new ListNode(4);
            list.head.next.next.next.next = new ListNode(5);
            list.head.next.next.next.next.next = new ListNode(6);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
            head=list.reverse(head);
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
    
        }
    }

Linked List before : 
    1 2 3 4 5 6 
    
    Linked List after: 
    6 5 4 3 2 1

## 3)Reverse a linked list by Tail Recursive Method: ##

The idea is to maintain **three pointers previous, current and next**, `recursively visit` every node and make links using these three pointers.

`Time Complexity`: `O(N)`, Visiting every node of the linked list of size N.  
`Auxiliary Space`: `O(N)`, Function call stack space

### Steps: ###

*  First update next with next node of current i.e. next = current->next
 *  Now make a reverse link from current node to previous node i.e. curr->next = prev
 *  If the visited node is the last node then just make a reverse link from the current node to previous node and update head.

package com.amy;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d) {
        
                val = d;
                next = null;
            }
        }
    
    
        // helper function: reverse a list
        ListNode reverse(ListNode curr, ListNode prev)
        {
        
            /*If head is initially null OR list is empty*/
            if (head == null)
                return head;
            /* If last node mark it head*/
            if (curr.next == null) {
        
                head = curr;
                /* Update next to prev node */
                curr.next = prev;
                return head;
            }
            /* Save curr->next node for recursive call */
            ListNode next1 = curr.next;
            /* and update next ..*/
            curr.next = prev;
            reverse(next1, curr);
            return head;
        }
    
    
        static void printList(ListNode node) {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.next;
            }
        }
    
    
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(2);
            list.head.next.next = new ListNode(3);
            list.head.next.next.next = new ListNode(4);
            list.head.next.next.next.next = new ListNode(5);
            list.head.next.next.next.next.next = new ListNode(6);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
            ListNode res =list.reverse(head, null);
            System.out.println(
                    "Linked List after: ");
            list.printList(res);
    
        }
    
    
    }

## 4)Reverse a linked list using Stack: ##

The idea is to store the all the nodes in the stack then make a reverse linked list.

### Steps: ###

*  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.

package com.amy;
    
    import java.util.Stack;
    
    /**
     * @author: Amy
     * @create: 2023-02-19 20:58
     **/
    class LinkedList {
        
    
        static ListNode head;
    
        static class ListNode {
        
    
            int val;
            ListNode next;
    
            ListNode(int d) {
        
                val = d;
                next = null;
            }
        }
    
    
        // Function to reverse the linked list
        static void reverse()
        {
        
    
            // Create a stack "s" of ListNode type
            Stack<ListNode> s = new Stack<>();
            ListNode temp = head;
            while (temp.next != null) {
        
                // Push all the nodes in to stack
                s.add(temp);
                temp = temp.next;
            }
            head = temp;
            while (!s.isEmpty()) {
        
                // Store the top value of stack in list
                temp.next = s.peek();
                // Pop the value from stack
                s.pop();
                // update the next pointer in the list
                temp = temp.next;
            }
            temp.next = null;
        }
    
    
        static void printList(ListNode node) {
        
            while (node != null) {
        
                System.out.print(node.val + " ");
                node = node.next;
            }
        }
    
    
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.head = new ListNode(1);
            list.head.next = new ListNode(2);
            list.head.next.next = new ListNode(3);
            list.head.next.next.next = new ListNode(4);
            list.head.next.next.next.next = new ListNode(5);
            list.head.next.next.next.next.next = new ListNode(6);
    
            System.out.println(
                    "Linked List before : ");
            list.printList(head);
            System.out.println("\n");
            list.reverse();
            System.out.println(
                    "Linked List after: ");
            list.printList(head);
    
        }
    
    
    }

Linked List before : 
    1 2 3 4 5 6 
    
    Linked List after: 
    6 5 4 3 2 1

[7136ecc0cb8612a1a253c24155074c23.gif_pic_center]: https://img-blog.csdnimg.cn/img_convert/7136ecc0cb8612a1a253c24155074c23.gif#pic_center
[dfe99044abe94b1a83c724d48aaeebde.png]: https://img-blog.csdnimg.cn/dfe99044abe94b1a83c724d48aaeebde.png
[e147394cc9684103b6ddfc4eb21abb73.png]: https://img-blog.csdnimg.cn/e147394cc9684103b6ddfc4eb21abb73.png