反向链接列表

￡神魔★判官ぃ 2023-10-05 19:25 17阅读 0赞

给定指向链表头节点的指针，任务是反转链表。我们需要通过更改节点之间的链接来反转列表。

**例子**：

> **输入**：以下链接列表的  
> 1-> 2-> 3-> 4-> NULL  
> **输出**：链接列表应更改为  
> 4-> 3-> 2-> 1-> NULL
> 
> **输入**：以下链接列表的  
> 1-> 2-> 3-> 4-> 5-> NULL  
> **输出**：链接列表应更改为  
> 5-> 4-> 3-> 2-> 1-> NULL
> 
> **输入**：NULL  
> **输出**：NULL
> 
> **输入**：1-> NULL  
> **输出**：1-> NULL  
>

**迭代法**

> 1.  将三个指针prev初始化为NULL，将curr初始化为head，将next初始化为NULL。
> 2.  遍历链接列表。循环执行以下操作。  
>     // //在更改下一个当前值之前，  
>     //存储下一个节点  
>     next = curr-> next  
>     //现在更改下一个当前  
>     // //这是实际反转发生的位置  
>     curr-> next = prev  
>     //将prev向前移动 一倍  
>     prev = curr  
>     curr =下一个

![db76ab0690faf25cc2f3c83e5c67e6de.gif][]

下面是上述方法的实现：

###  ###

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:454px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program for reversing the linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>class</code> <code>LinkedList { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>Node head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>class</code> <code>Node { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node(</code><code>int</code> <code>d)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>data = d;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>next = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* Function to reverse the linked list */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node reverse(Node node)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node prev = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node current = node;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(current != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>next = current.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current.next = prev;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>prev = current;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>current = next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node = prev;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>node;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// prints content of double linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>printList(Node node)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(node != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(node.data + </code><code>" "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node = node.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Driver Code</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>LinkedList list = </code><code>new</code> <code>LinkedList();</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head = </code><code>new</code> <code>Node(</code><code>85</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next = </code><code>new</code> <code>Node(</code><code>15</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next = </code><code>new</code> <code>Node(</code><code>4</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next = </code><code>new</code> <code>Node(</code><code>20</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Given Linked list"</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = list.reverse(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>""</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Reversed linked list "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// This code has been contributed by Mayank Jaiswal</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

###  ###

**输出：**

给定链表
    85 15 4 20 
    反向链接列表 
    20 4 15 85

**时间复杂度：** O（n）  
**空间复杂度：** O（1）  
**递归方法：**

1）将清单分为两部分-第一个节点和 
          链表的其余部分。
       2）调用反向链接列表的其余部分。
       3）将休息链接到第一位。
       4）固定头指针

![链表反向][c42997b58f1bb0fb445bc20c05d0a4d5.gif]

###  ###

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:421px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Recursive Java program to reverse</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// a linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>class</code> <code>recursion { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>Node head; </code><code>// head of list </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>class</code> <code>Node { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node(</code><code>int</code> <code>d) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>data = d; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>next = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>Node reverse(Node head) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code> <code>|| head.next == </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>head; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* reverse the rest list and put </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>the first element at the end */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node rest = reverse(head.next); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head.next.next = head; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* tricky step -- see the diagram */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head.next = </code><code>null</code><code>; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* fix the head pointer */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>rest; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* Function to print linked list */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>void</code> <code>print() </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node temp = head; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(temp != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(temp.data + </code><code>" "</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = temp.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println();</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>void</code> <code>push(</code><code>int</code> <code>data) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node temp = </code><code>new</code> <code>Node(data); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp.next = head; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = temp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>} </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>/* Driver program to test above function*/</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>static</code> <code>void</code> <code>main(String args[]) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* Start with the empty list */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>push(</code><code>20</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>push(</code><code>4</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>push(</code><code>15</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>push(</code><code>85</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Given linked list"</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>print(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = reverse(head); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Reversed Linked list"</code><code>); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>print(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// This code is contributed by Prakhar Agarwal</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

###  ###

**输出：**

给定链表
    85 15 4 20 
    反向链接列表
    20 4 15 85

**时间复杂度：** O（n）  
**空间复杂度：** O（1）

**一种更简单的尾递归方法**

下面是此方法的实现。

###  ###

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:496px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program for reversing the Linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>class</code> <code>LinkedList { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>Node head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>static</code> <code>class</code> <code>Node { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node(</code><code>int</code> <code>d)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>data = d;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>next = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// A simple and tail recursive function to reverse</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// a linked list.&nbsp; prev is passed as NULL initially.</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node reverseUtil(Node curr, Node prev)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/*If head is initially null OR list is empty*/</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* If last node mark it head*/</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(curr.next == </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = curr;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* Update next to prev node */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr.next = prev;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* Save curr-&gt;next node for recursive call */</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next1 = curr.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/* and update next ..*/</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>curr.next = prev;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>reverseUtil(next1, curr);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// prints content of double linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>void</code> <code>printList(Node node)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(node != </code><code>null</code><code>) { </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(node.data + </code><code>" "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>node = node.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Driver Code</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>LinkedList list = </code><code>new</code> <code>LinkedList();</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head = </code><code>new</code> <code>Node(</code><code>1</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next = </code><code>new</code> <code>Node(</code><code>2</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next = </code><code>new</code> <code>Node(</code><code>3</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next = </code><code>new</code> <code>Node(</code><code>4</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next.next = </code><code>new</code> <code>Node(</code><code>5</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next.next.next = </code><code>new</code> <code>Node(</code><code>6</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next.next.next.next</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>= </code><code>new</code> <code>Node(</code><code>7</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.head.next.next.next.next.next.next.next</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>= </code><code>new</code> <code>Node(</code><code>8</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Original Linked list "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node res = list.reverseUtil(head, </code><code>null</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>""</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>""</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Reversed linked list "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>list.printList(res);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// This code has been contributed by Mayank Jaiswal</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

###  ###

**输出量**

给定链表
    1 2 3 4 5 6 7 8 
    
    反向链表
    8 7 6 5 4 3 2 1

**使用堆栈：**

*  将节点（值和地址）存储在堆栈中，直到输入所有值。
 *  完成所有输入后，将Head指针更新到最后一个位置（即最后一个值）。
 *  开始弹出节点（值和地址）并以相同顺序存储它们，直到堆栈为空。
 *  用NULL更新堆栈中最后一个节点的下一个指针。

<table style="width:631.844px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:baseline;width:429px;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Java program for above approach</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>import</code> <code>java.util.*;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>class</code> <code>GFG{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Create a class Node to enter </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// values and address in the list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>class</code> <code>Node </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>data;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>};</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>Node head = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Function to reverse the </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>void</code> <code>reverseLL()</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{&nbsp;&nbsp; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Create a stack "s" </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// of Node type</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Stack&lt;Node&gt; s = </code><code>new</code> <code>Stack&lt;&gt;(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node temp = head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(temp.next != </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Push all the nodes </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// in to stack</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s.add(temp); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = temp.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = temp;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(!s.isEmpty()) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Store the top value of</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// stack in list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp.next = s.peek(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// Pop the value from stack</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s.pop(); </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// update the next pointer in the</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// in the list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = temp.next; </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp.next = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Function to Display </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// the elements in List</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>void</code> <code>printlist(Node temp) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(temp != </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(temp.data+ </code><code>" "</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp = temp.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Program to insert back of the </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// linked list</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>static</code> <code>void</code> <code>insert_back( </code><code>int</code> <code>value)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// we have used insertion at back method</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// to enter values in the list.(eg:</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// head.1.2.3.4.Null)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node temp = </code><code>new</code> <code>Node();</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp.data = value;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>temp.next = </code><code>null</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// If *head equals to null</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(head == </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>head = temp;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Node last_node = head;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(last_node.next != </code><code>null</code><code>) </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>last_node = last_node.next;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>last_node.next = temp;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// Driver Code</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args)</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>{ </code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>insert_back( </code><code>1</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>insert_back( </code><code>2</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>insert_back(</code><code>3</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>insert_back( </code><code>4</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"Given linked list\n"</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printlist(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>reverseLL();</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"\nReversed linked list\n"</code><code>);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>printlist(head);</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>}</code></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;">&nbsp;</span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#40424e;"><code>// This codeis contributed by gauravrajput1</code></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

###  ###

**输出量**

给定链表
    1 2 3 4 
    反向链表
    4 3 2 1

[db76ab0690faf25cc2f3c83e5c67e6de.gif]: https://img-blog.csdnimg.cn/img_convert/db76ab0690faf25cc2f3c83e5c67e6de.gif
[c42997b58f1bb0fb445bc20c05d0a4d5.gif]: https://img-blog.csdnimg.cn/img_convert/c42997b58f1bb0fb445bc20c05d0a4d5.gif