java反轉鏈表的多種解決方法舉例詳解

更新時間：2025年04月22日 09:25:43 作者：DIO?KING

這篇文章主要介紹了java反轉鏈表的多種解決方法,分別是使用棧、雙指針和遞歸,每種方法都有其實現(xiàn)原理和代碼示例,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

反轉鏈表的三種方式

1，使用棧解決

棧是最容易的一種方式了，因為棧是先進后出。實現(xiàn)原理就是把鏈表節(jié)點一個個入棧，全部入棧之后再一個個出棧，出棧的時候在把節(jié)點按照出棧的順序組成一個新的鏈表。

原理如圖：

代碼如下：

public ListNode ReverseList(ListNode head){
	Stack<ListNode> stack = new Stack<>();
	//把全部節(jié)點都壓入棧中
	while(head != null){
		stack.push(head);
		head = head.next;
	}
	//如果stack棧里面沒有數(shù)據(jù)，說明head是一個空指針，因此可以直接返回
	//不需要進行后續(xù)計算
	if(stack.isEmpty()){
		return null;
	}
	ListNode node = stack.pop();//出棧的第一個節(jié)點成為第一個新鏈表的第一個節(jié)點
	ListNode dummy = node; //保留頭節(jié)點，用于最后的返回
	//把棧中的節(jié)點全部出棧，然后重新連成一個新的鏈表
	while(!stack.isEmpty()){
		node.next = stack.pop();
		node = node.next;//更換鏈表的最后一個元素
	}
	//最后一個節(jié)點就是反轉前的頭節(jié)點，需要讓他的next為null
	//不然可能構成環(huán)
	node.next = null;
	return dummy;//最后返回保存好的頭節(jié)點
}

2，雙指針實現(xiàn)

利用兩個指針來保存鏈表中數(shù)據(jù)，一個指針用來存儲當前節(jié)點中next元素中更改后的值，另一個指針來指向下一個需要更改節(jié)點的地址。

原理如圖：

代碼如下：

public ListNode ReverseList(ListNode head) {
	//當前節(jié)點中next元素改變后的值
	//初始值為null是因為更改后 原第一個元素 改后最后一個元素
	//next指向的值為null
	ListNode ChangeNode = null;
	while (head != null) {
	    //先保存當前訪問的節(jié)點的下一個節(jié)點
		//留著while循環(huán)最后更新數(shù)據(jù)并且
		ListNode nextNode = head.next;
		//把當前節(jié)點中next元素進行更改，使其可以指向前一個元素
		head.next = ChangeNode;
		//更新ChangeNode指針，用于下一次節(jié)點next元素更新
		ChangeNode = head;
		//更新節(jié)點，去往下一個節(jié)點
		head = nextNode;
	}
	//循環(huán)之后ChangeNode指向的值為 原最后一個節(jié)點 改后第一個節(jié)點
	//所以返回ChangeNode就是改后的頭節(jié)點
	return ChangeNode;
}

3，遞歸實現(xiàn)

遞歸實現(xiàn)是最難的，理由是遞歸本身很難理解。我認為遞歸的本質是通過不斷的改變參數(shù)找到問題的原點，再進行返回。邏輯處理部分則是在不斷找尋原點的過程中，或者是找到原點后在返回的過程中進行的。這個題目既可以在找原點的過程中設置邏輯處理，也可以在返還的過程中進行邏輯處理。

找原點的過程中設置邏輯處理：

public ListNode ReverseList(ListNode head) {
    //Reverse函數(shù)的兩個參數(shù)的意思是，當前節(jié)點和上一個節(jié)點
    //head是原本函數(shù)的頭節(jié)，null是更改后頭節(jié)點指向的值
    return Reverse(head, null);
}

public ListNode Reverse(ListNode nowNode, ListNode lastNode) {、
    //當前節(jié)點是null
    //說明上一個節(jié)點是最后一個節(jié)點
    if (nowNode == null) { 
        return lastNode;  
    }
    //先保存下一個地址的位置
    ListNode next = nowNode.next;
    //讓當前節(jié)點指向上一個節(jié)點
    nowNode.next = lastNode;

    //處理完這個節(jié)點的邏輯之后開始前往下一個節(jié)點
    return Reverse(next, nowNode);
}

返還的過程中進行邏輯處理：

	public ListNode ReverseList(ListNode head){
		//當前節(jié)點的next元素沒有指向下一個元素的時候說明這是最后一個元素
		if(head == null || head.next == null){
			return head;
		}
		//找到最后一個元素，并開始一層一層的往上傳遞
		ListNode last = ReverseList(head.next);
		//把下一個元素指向的元素改為自己
		//（因為遞歸條件的影響當前的元素只可能是反轉后第二個元素之后的元素，
		// 所以head.next.next不會越界）
		head.next.next = head;
		//并且清除當前指向的節(jié)點，防止可能的問題（成環(huán)）
		head.next = null;
        //傳遞最后一個元素
		return last;
	}

建議先看懂前面兩個方法再來看最后的遞歸，先看懂這個題目的基本處理邏輯。

后面兩個解法的本質是指針的運用，Java對這方面沒有很好的解釋，所以可能會有點難理解