使用迭代方法反轉(zhuǎn)鏈表

以下是迭代方法中涉及的一些步驟。

第 1 步：取三個(gè)指針(previous，current，next)。

前一個(gè) = NULL，當(dāng)前 = 頭，下一個(gè) = NULL。

第 2 步：使用循環(huán)遍歷鏈表，并執(zhí)行以下操作。

// 在改變當(dāng)前的下一個(gè)之前，           
 // 保留下一個(gè)節(jié)點(diǎn)            
下一個(gè) = 當(dāng)前 -> 下一個(gè)           
// 現(xiàn)在改變當(dāng)前的下一個(gè)            
// 這是反轉(zhuǎn)發(fā)生的地方            
當(dāng)前 -> 下一個(gè) = 上一個(gè)            
// 將上一個(gè)和當(dāng)前向前移動(dòng)一步             
以前的 = 當(dāng)前的           
當(dāng)前 = 下一個(gè)   

執(zhí)行

下面的代碼顯示了在上面定義的步驟的幫助下實(shí)現(xiàn)鏈表的反轉(zhuǎn)。

文件名： LinkedListIterative.java

公共類 LinkedListIterative    
{    
// head是鏈表的第一個(gè)節(jié)點(diǎn)  
靜態(tài) LinkedListNode 頭；    
// 創(chuàng)建鏈表節(jié)點(diǎn)的類  
// 鏈表的一個(gè)節(jié)點(diǎn)獲取兩個(gè)東西：一個(gè)是節(jié)點(diǎn)的值  
// other 是指向另一個(gè)節(jié)點(diǎn)的指針  
靜態(tài)類 LinkedListNode    
{   
整 數(shù)值；   
接下來是LinkedListNode；   
// 類 LinkedListNode 的構(gòu)造函數(shù)  
LinkedListNode（整數(shù) 編號(hào)）  
{  
瓦爾=沒有；  
下一個(gè)= 空；  
}  
}    
// 反轉(zhuǎn)鏈表的方法  
LinkedListNode reverse(LinkedListNode節(jié)點(diǎn))  
{  
// 進(jìn)行初始化   
// 按照定義的步驟   
LinkedListNode 前一個(gè) =  null ;  
LinkedListNode 當(dāng)前 = 節(jié)點(diǎn)；  
LinkedListNode next =  null ;      
while  (curr !=  null )   
{  
next = curr.next;  
當(dāng)前.下一個(gè)=上一個(gè)；  
以前的=當(dāng)前；  
當(dāng)前=下一個(gè)；  
}  
節(jié)點(diǎn)=前一個(gè)；  
返回 節(jié)點(diǎn)；  
}    
//顯示鏈表的內(nèi)容  
void  printList(LinkedListNode nde)  
{  
while  (nde !=  null )   
{  
System.out.print(nde.val +  " " );  
nde = nde.next;  
}  
}    
// 主要方法  
public static void  main(String argvs[])    
{  
// 創(chuàng)建類 LinkedListIterative 的對(duì)象  
LinkedListIterative listObj =  new  LinkedListIterative();    
// 4 -> 空  
listObj.head =  new  LinkedListNode( 4 );    
// 4 -> 6 -> 空值  
listObj.head.next =  new  LinkedListNode( 6 );   
// 4 -> 6 -> 7 -> 空值  
listObj.head.next.next =  new  LinkedListNode( 7 );   
// 4 -> 6 -> 7 -> 1-> NULL  
listObj.head.next.next.next =  new  LinkedListNode( 1 );   
// 4 -> 6 -> 7 -> 1-> 5 -> NULL  
listObj.head.next.next.next.next =  new  LinkedListNode( 5 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> NULL  
listObj.head.next.next.next.next.next =  new  LinkedListNode( 8 );   
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> NULL  
listObj.head.next.next.next.next.next.next =  new  LinkedListNode( 3 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> 2 -> NULL  
listObj.head.next.next.next.next.next.next.next =  new  LinkedListNode( 2 );      
System.out.println( "反轉(zhuǎn)前的鏈表為：" );  
listObj.printList（頭）；  
head = listObj.reverse(head);  
System.out.println( "\n" );  
System.out.println( "反轉(zhuǎn)后鏈表為：" );  
listObj.printList（頭）；  
}  
}  

輸出：

反轉(zhuǎn)前的鏈表為：
4 6 7 1 5 8 3 2
反轉(zhuǎn)后鏈表為：
2 3 8 5 1 7 6 4

時(shí)間和空間復(fù)雜度：上述程序的時(shí)間復(fù)雜度為 O(n)，而空間復(fù)雜度為 O(1)，其中 n 表示列表中存在的節(jié)點(diǎn)總數(shù)。

使用遞歸方法反轉(zhuǎn)鏈表

以下是遞歸方法中涉及的一些步驟。

第 1 步：將給定的列表分成兩部分 - 第一個(gè)節(jié)點(diǎn)和鏈表的其余部分。

第 2 步：為鏈表的剩余部分調(diào)用 reverseList() 方法。

第 3 步：將其余部分加入第一個(gè)。

第四步：固定頭指針。

執(zhí)行

下面的代碼顯示了在上面定義的步驟的幫助下實(shí)現(xiàn)鏈表的反轉(zhuǎn)。

文件名： LinkedListRecursive.java

公共類 LinkedListRecursive    
{  
// 列表的第一個(gè)節(jié)點(diǎn)或頭部  
靜態(tài) LinkedListNode 頭；   
靜態(tài)類 LinkedListNode    
{  
// 用于包含節(jié)點(diǎn)的值  
整 數(shù)值；    
// next 指針指向鏈表的另一個(gè)節(jié)點(diǎn)或 null  
接下來是LinkedListNode；   
// 類的構(gòu)造函數(shù)  
鏈表節(jié)點(diǎn)（int  d）  
{  
// 賦值  
值=d；  
下一個(gè)= 空；  
}  
}    
// 實(shí)際發(fā)生列表反轉(zhuǎn)的方法  
public  LinkedListNode reverseList(LinkedListNode head)  
{  
// 如果頭部為空或列表  
// 只包含一個(gè)元素然后反轉(zhuǎn)列表  
// 對(duì)列表沒有任何影響。因此，我們   
// 不做任何操作就可以返回原來的列表  
如果 (head ==  null  || head.next ==  null )  
{  
返回 頭；  
}    
// 反轉(zhuǎn)列表的其余部分 (r) 并放置  
// 列表的第一個(gè)元素在最后   
LinkedListNode r = reverseList(head.next);  
head.next.next = 頭；      
head.next =  null ;    
//固定頭指針  
返回 r；  
}    
/* 顯示鏈表的方法 */  
public void  printList(LinkedListNode h)   
{  
鏈表節(jié)點(diǎn) t = h;  
while  (t !=  null )   
{  
System.out.print(t.val +  " " );    
// 移動(dòng)到下一個(gè)節(jié)點(diǎn)  
t = t.下一個(gè)；  
}    
System.out.println();  
}      
// 主要方法  
public static void  main(String argvs[])    
{  
// 創(chuàng)建類 LinkedListRecursive 的對(duì)象  
LinkedListRecursive listObj =  new  LinkedListRecursive();    
// 4 -> 空  
listObj.head =  new  LinkedListNode( 4 );    
// 4 -> 6 -> 空值  
listObj.head.next =  new  LinkedListNode( 6 );    
// 4 -> 6 -> 7 -> 空值  
listObj.head.next.next =  new  LinkedListNode( 7 );    
// 4 -> 6 -> 7 -> 1-> NULL  
listObj.head.next.next.next =  new  LinkedListNode( 1 );    
// 4 -> 6 -> 7 -> 1-> 5 -> NULL  
listObj.head.next.next.next.next =  new  LinkedListNode( 5 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> NULL  
listObj.head.next.next.next.next.next =  new  LinkedListNode( 8 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> NULL  
listObj.head.next.next.next.next.next.next =  new  LinkedListNode( 3 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> 2 -> NULL  
listObj.head.next.next.next.next.next.next.next =  new  LinkedListNode( 2 );      
System.out.println( "反轉(zhuǎn)前的鏈表為：" );  
listObj.printList（頭）；  
head = listObj.reverseList(head);  
System.out.println( " " );  
System.out.println( "反轉(zhuǎn)后鏈表為：" );  
listObj.printList（頭）；  
}  
}  

輸出：

反轉(zhuǎn)前的鏈表為：
4 6 7 1 5 8 3 2
反轉(zhuǎn)后鏈表為：
2 3 8 5 1 7 6 4

時(shí)間和空間復(fù)雜度：上述程序的時(shí)間復(fù)雜度為 O(n)，而空間復(fù)雜度為 O(1)，其中 n 表示列表中存在的節(jié)點(diǎn)總數(shù)。請(qǐng)注意，由于遞歸，上述程序使用了內(nèi)置堆棧。為了簡(jiǎn)單起見，我們忽略了內(nèi)置堆棧占用的空間。

使用堆棧反轉(zhuǎn)鏈表

下面是使用棧對(duì)鏈表進(jìn)行反轉(zhuǎn)時(shí)使用的步驟。

第 1 步：將節(jié)點(diǎn)的值保留在堆棧中，直到輸入所有節(jié)點(diǎn)的值。

第 2 步：使用列表最后一個(gè)節(jié)點(diǎn)的值更新 Head 指針。

第 3 步：繼續(xù)從堆棧中刪除節(jié)點(diǎn)的值，并開始將它們附加到頭節(jié)點(diǎn)，直到堆棧為空。

第 4 步：確保附加工作完成后，列表的最后一個(gè)節(jié)點(diǎn)指向 NULL。

執(zhí)行

下面的代碼顯示了在上面定義的步驟的幫助下實(shí)現(xiàn)鏈表的反轉(zhuǎn)。

文件名： LinkedListStack.java

// 重要的導(dǎo)入語句  
導(dǎo)入 java.util.*;   
公共類 LinkedListStack   
{    
// 列表的第一個(gè)節(jié)點(diǎn)或頭部  
靜態(tài) LinkedListNode 頭；     
靜態(tài)類 LinkedListNode    
{  
// 用于包含節(jié)點(diǎn)的值  
整 數(shù)值；   
// next 指針指向鏈表的另一個(gè)節(jié)點(diǎn)或 null  
接下來是LinkedListNode；    
// 類的構(gòu)造函數(shù)  
鏈表節(jié)點(diǎn)（int  d）  
{  
// 賦值  
值=d；  
下一個(gè)= 空；  
}  
}    
// 實(shí)際發(fā)生列表反轉(zhuǎn)的方法  
public  LinkedListNode reverseList(LinkedListNode head, Stack<Integer> stk)  
{  
// 如果頭部為空或列表  
// 只包含一個(gè)元素然后反轉(zhuǎn)列表  
// 對(duì)列表沒有任何影響。因此，我們   
// 不做任何操作就可以返回原來的列表  
如果 (head ==  null  || head.next ==  null )  
{  
返回 頭；  
}    
// 遍歷列表并放入節(jié)點(diǎn)的值  
//入棧stk  
while (head !=  null )  
{  
    stk.push(head.val);  
    head = head.next;  
}    
// head1 指的是反轉(zhuǎn)的第一個(gè)節(jié)點(diǎn)   
// 鏈表  
鏈表節(jié)點(diǎn) head1 =  null ;    
while (stk.empty() ==  false )   {  
如果（頭== 空）  
{  
// 創(chuàng)建第一個(gè)節(jié)點(diǎn)  
// 反向鏈表  
head1 =  new  LinkedListNode(stk.peek());  
頭=頭1；  
stk.pop();  
}  
別的  
{  
// 創(chuàng)建反向的剩余節(jié)點(diǎn)   
// 鏈表  
head.next =  new  LinkedListNode(stk.peek());  
stk.pop();  
head = head.next;  
}      
}    
// 返回第一個(gè)節(jié)點(diǎn)   
// 反向鏈表  
返回 頭1；  
}    
/* 顯示鏈表的方法 */  
public void  printList(LinkedListNode h)   
{  
鏈表節(jié)點(diǎn) t = h;  
while  (t !=  null )   
{  
System.out.print(t.val +  " " );    
// 移動(dòng)到下一個(gè)節(jié)點(diǎn)  
t = t.下一個(gè)；  
}    
System.out.println();  
}    
// 主要方法  
public static void  main(String argvs[])    
{  
// 創(chuàng)建類 LinkedListStack 的對(duì)象  
LinkedListStack listObj =  new  LinkedListStack();    
// 4 -> 空  
listObj.head =  new  LinkedListNode( 4 );    
// 4 -> 6 -> 空值  
listObj.head.next =  new  LinkedListNode( 6 );    
// 4 -> 6 -> 7 -> 空值  
listObj.head.next.next =  new  LinkedListNode( 7 );    
// 4 -> 6 -> 7 -> 1-> NULL  
listObj.head.next.next.next =  new  LinkedListNode( 1 );    
// 4 -> 6 -> 7 -> 1-> 5 -> NULL  
listObj.head.next.next.next.next =  new  LinkedListNode( 5 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> NULL  
listObj.head.next.next.next.next.next =  new  LinkedListNode( 8 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> NULL  
listObj.head.next.next.next.next.next.next =  new  LinkedListNode( 3 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> 2 -> NULL  
listObj.head.next.next.next.next.next.next.next =  new  LinkedListNode( 2 );    
// 創(chuàng)建 Stack 類的對(duì)象  
// 創(chuàng)建的棧將為空  
堆棧<整數(shù)> stk = 新 堆棧<整數(shù)>();    
System.out.println( "反轉(zhuǎn)前的鏈表為：" );  
listObj.printList（頭）；    
head = listObj.reverseList(head, stk);  
System.out.println( " " );  
System.out.println( "反轉(zhuǎn)后鏈表為：" );  
listObj.printList（頭）；    
}  
}  

輸出：

反轉(zhuǎn)前的鏈表為：
4 6 7 1 5 8 3 2
反轉(zhuǎn)后鏈表為：
2 3 8 5 1 7 6 4

時(shí)間和空間復(fù)雜度：上述程序的時(shí)間復(fù)雜度為 O(n)，而空間復(fù)雜度也是 O(n)，其中 n 表示列表中存在的節(jié)點(diǎn)總數(shù)。

使用數(shù)組反轉(zhuǎn)鏈表

以下是使用數(shù)組對(duì)鏈表進(jìn)行反轉(zhuǎn)時(shí)使用的步驟。

第 1 步：計(jì)算給定列表中存在的節(jié)點(diǎn)數(shù)。

第 2 步：創(chuàng)建一個(gè)整數(shù)數(shù)組，使數(shù)組的大小等于列表的大小。

第 3 步：遍歷列表并使用節(jié)點(diǎn)的值從左到右填充數(shù)組。

第 4 步：從數(shù)組的末尾開始，逐個(gè)取出數(shù)組元素并從中創(chuàng)建一個(gè)列表，這樣數(shù)組的最后一個(gè)元素構(gòu)成列表的頭部。數(shù)組的倒數(shù)第二個(gè)元素構(gòu)成列表的第二個(gè)節(jié)點(diǎn)，依此類推。

執(zhí)行

下面的代碼顯示了在上面定義的步驟的幫助下實(shí)現(xiàn)鏈表的反轉(zhuǎn)。

文件名： LinkedListArray.java

// 重要的導(dǎo)入語句  
導(dǎo)入 java.util.*;    
公共類 LinkedListArray   
{    
// 列表的第一個(gè)節(jié)點(diǎn)或頭部  
靜態(tài) LinkedListNode 頭；     
靜態(tài)類 LinkedListNode    
{  
// 用于包含節(jié)點(diǎn)的值  
整 數(shù)值；    
// next 指針指向鏈表的另一個(gè)節(jié)點(diǎn)或 null  
接下來是LinkedListNode；    
// 類的構(gòu)造函數(shù)  
鏈表節(jié)點(diǎn)（int  d）  
{  
// 賦值  
值=d；  
下一個(gè)= 空；  
}  
}    
// 計(jì)算節(jié)點(diǎn)總數(shù)的方法   
//存在于鏈表中  
public int  countNodes（LinkedListNode 頭）   
{  
// cnt 存儲(chǔ)節(jié)點(diǎn)總數(shù)  
//存在于鏈表中  
int  cnt =  0 ;  
while (head !=  null )  
{  
// 計(jì)數(shù)加 1  
cnt = cnt +  1 ;    
// 將頭部向前移動(dòng)一步  
head = head.next;  
}    
返回 cnt；  
}    
// 實(shí)際發(fā)生列表反轉(zhuǎn)的方法  
public  LinkedListNode reverseList(LinkedListNode head,  int  size)  
{  
// 用于存儲(chǔ)鏈表節(jié)點(diǎn)值的數(shù)組  
int  arr[] =  new int [大小];     
// 循環(huán)填充數(shù)組  
for ( int  i =  0 ; i < 大小; i++)  
{  
arr[i] = head.val;  
head = head.next;  
}    
// i 存儲(chǔ)數(shù)組 arr 的最后一個(gè)索引  
int  i = 大小 -  1 ;    
// head1 指的是鏈表的第一個(gè)節(jié)點(diǎn)  
鏈表節(jié)點(diǎn) head1 =  null ;      
而（我> =  0 ）  
{        
如果（head1 ==  null ）  
{  
// 創(chuàng)建反向鏈表的第一個(gè)節(jié)點(diǎn)  
head1 =  new  LinkedListNode(arr[i]);  
頭=頭1；  
}  
別的  
{  
// 創(chuàng)建并追加剩余的節(jié)點(diǎn)   
// 反向鏈表的head1  
head.next =  new  LinkedListNode(arr[i]);  
head = head.next;  
}  
// 從頭到尾迭代   
// 因此，將 i 減 1  
我 = 我 -  1 ;    
}    
// 返回第一個(gè)節(jié)點(diǎn)   
// 反向鏈表  
返回 頭1；      
}      
/* 顯示鏈表的方法 */  
public void  printList(LinkedListNode h)   
{  
鏈表節(jié)點(diǎn) t = h;  
while  (t !=  null )   
{  
System.out.print(t.val +  " " );    
// 移動(dòng)到下一個(gè)節(jié)點(diǎn)  
t = t.下一個(gè)；  
}    
System.out.println();  
}      
// 主要方法  
public static void  main(String argvs[])    
{  
// 創(chuàng)建類 LinkedListArray 的對(duì)象  
LinkedListArray listObj =  new  LinkedListArray();    
// 4 -> 空  
listObj.head =  new  LinkedListNode( 4 );    
// 4 -> 6 -> 空值  
listObj.head.next =  new  LinkedListNode( 6 );    
// 4 -> 6 -> 7 -> 空值  
listObj.head.next.next =  new  LinkedListNode( 7 );    
// 4 -> 6 -> 7 -> 1-> NULL  
listObj.head.next.next.next =  new  LinkedListNode( 1 );    
// 4 -> 6 -> 7 -> 1-> 5 -> NULL  
listObj.head.next.next.next.next =  new  LinkedListNode( 5 );   
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> NULL  
listObj.head.next.next.next.next.next =  new  LinkedListNode( 8 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> NULL  
listObj.head.next.next.next.next.next.next =  new  LinkedListNode( 3 );    
// 4 -> 6 -> 7 -> 1-> 5 -> 8 -> 3 -> 2 -> NULL  
listObj.head.next.next.next.next.next.next.next =  new  LinkedListNode( 2 );     
System.out.println( "反轉(zhuǎn)前的鏈表為：" );  
listObj.printList（頭）；   
// size 是節(jié)點(diǎn)總數(shù)  
//存在于鏈表中  
int  size = listObj.countNodes(head);    
head = listObj.reverseList(head, size);  
System.out.println( " " );  
System.out.println( "反轉(zhuǎn)后鏈表為：" );  
listObj.printList（頭）；    
}  
}  

輸出：

反轉(zhuǎn)前的鏈表為：
4 6 7 1 5 8 3 2
反轉(zhuǎn)后鏈表為：
2 3 8 5 1 7 6 4

時(shí)間和空間復(fù)雜度：上述程序的時(shí)間復(fù)雜度為 O(n)，而空間復(fù)雜度也是 O(n)，其中 n 表示列表中存在的節(jié)點(diǎn)總數(shù)。