单链表的反转

小灰灰 2021-10-01 04:28 354阅读 0赞

[ ][Link 1]

单链表是一种常见的数据结构，由一个个节点通过指针方式连接而成，每个节点由两部分组成：一是数据域，用于存储节点数据。二是指针域，用于存储下一个节点的地址。在Java中定义如下：

public class Node { 
       
       private Object data; //数据域 
       private Node next; //指针域 
       
       public Node(Object data){ 
       this. data = data; 
       } 
       
       public Node(Object data,Node next){ 
       this. data = data; 
       this.next = next; 
       } 
       
       public Object getData() { 
       return data; 
       } 
       
       public void setData(Object data) { 
       this. data = data; 
       } 
       
       public Node getNext() { 
       return next; 
       } 
       
       public void setNext(Node next) { 
       this.next = next; 
       } 
       
       }

单链表的反转操作是面试java开发中常考的题目，笔者面试时曾被这道题虐过qaq，之后痛定思痛，研究了一番之后，写出来与大家分享。

先说下思路：所谓的单链表反转，就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。但由于单链表没有指向前一个节点的指针域，因此我们需要增加一个**指向前一个节点的指针pre**，用于存储每一个节点的前一个节点。此外，还需要定义一个**保存当前节点的指针cur**，**以及下一个节点的next。**定义好这三个指针后，遍历单链表，将当前节点的指针域指向前一个节点，之后将定义三个指针往后移动，直至遍历到最后一个节点停止。

OK，说完思路，直接上代码。

public static Node reverseListNode(Node head){ 
       //单链表为空或只有一个节点，直接返回原单链表 
       if (head == null || head.getNext() == null){ 
       return head; 
       } 
       //前一个节点指针 
       Node preNode = null; 
       //当前节点指针 
       Node curNode = head; 
       //下一个节点指针 
       Node nextNode = null; 
       
       while (curNode != null){ 
       nextNode = curNode.getNext(); //nextNode 指向下一个节点 
       curNode.setNext(preNode); //将当前节点next域指向前一个节点 
       preNode = curNode; //preNode 指针向后移动 
       curNode = nextNode; //curNode指针向后移动 
       } 
       
       return preNode; 
       }

[Link 1]: http://creativecommons.org/licenses/by-sa/4.0/