链表反转

九州暮云

修改于 2019-08-21 11:34:14

1.1K0

修改于 2019-08-21 11:34:14

文章被收录于专栏：九州牧云九州牧云

链表反转的实现可以用两种方式：遍历法和递归法，最终的效果如下：

原始链表：->30->25->20->15->10->5
反转后的链表：->5->10->15->20->25->30

遍历法

遍历法过程如下：

创建三个节点：currNode、prevNode和nextNode，并初始化currNode = head、nextNode = null和prevNode = null；
从head头结点开始遍历链表，当currNode!=null时，一个个反转链表的指针：

while(currNode!=null){
     nextNode = currNode.next;
     currNode.next = prevNode;
     prevNode = currNode;
     currNode = nextNode;
}

设置head = prevNode。

实现过程如下图：

实现代码如下：

public class ReverseLinkedList {
	public static void main (String[] args) throws java.lang.Exception
	{
		LinkedListT a = new LinkedListT();
		a.addAtBegin(5);
		a.addAtBegin(10);
		a.addAtBegin(15);
		a.addAtBegin(20);
		a.addAtBegin(25);
		a.addAtBegin(30);
		a.display(a.head);
		a.reverseIterative(a.head);	}
}
class Node{
	public int data;
	public Node next;
	public Node(int data){
		this.data = data;
		this.next = null;
	}
}
class LinkedListT{
	public Node head;
	public LinkedListT(){
		head=null;
	}

	public void addAtBegin(int data){
		Node n = new Node(data);
		n.next = head;
		head = n;
	}
	
	public void reverseIterative(Node head){
		Node currNode = head;
		Node nextNode = null;
		Node prevNode = null;

		while(currNode!=null){
			nextNode = currNode.next;
			currNode.next = prevNode;//反转：使链表的下一个节点和上一个节点相连
			prevNode = currNode;//保存反转后的链表
			currNode = nextNode;
		}
		head = prevNode;
		System.out.println("\n Reverse Through Iteration");
		display(head);
	}

	public void display(Node head){
		//
		Node currNode = head;
		while(currNode!=null){
			System.out.print("->" + currNode.data);
			currNode=currNode.next;
		}
	}
}

递归法

递归法过程如下：

通过递归的方式，找到链表的结束节点，并保存在head变量中；
这时，剩余的链表节点会被保存在一个栈结构里面，接下来我们使用递归的方式从栈里面弹出这些节点，将它们和head节点一个个连接起来。

实现过程如下图：

实现代码如下：

public class ReverseLinkedList {
    public static void main (String[] args) throws java.lang.Exception
    {
        LinkedListT a = new LinkedListT();
        a.addAtBegin(5);
        a.addAtBegin(10);
        a.addAtBegin(15);
        a.addAtBegin(20);
        a.addAtBegin(25);
        a.addAtBegin(30);
        a.display(a.head);
        a.reverseRecur(a.head); 
    }
}
class Node{
    public int data;
    public Node next;
    public Node(int data){
        this.data = data;
        this.next = null;
    }
}
class LinkedListT{
    public static Node head=null;
    public LinkedListT(){
        head=null;
    }

    public void addAtBegin(int data){
        Node n = new Node(data);
        n.next = head;
        head = n;
    }
    
    public Node reverseRecur(Node current){
		if(current==null){
			return null;
		}
		if(current.next==null){
			head = current;
			return null;
		}
		reverseRecur(current.next);
		current.next.next = current;
		current.next = null;
		return head;
	 }

    public void display(Node head){
        //
        Node currNode = head;
        while(currNode!=null){
            System.out.print("->" + currNode.data);
            currNode=currNode.next;
        }
    }
}

编译自：Reverse a Linked List

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

node.js