使用迭代方法反轉鏈表

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

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

前一個 = NULL，當前 = 頭，下一個 = NULL。

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

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

執(zhí)行

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

文件名： LinkedListIterative.java

公共類 LinkedListIterative    
{    
// head是鏈表的第一個節(jié)點  
靜態(tài) LinkedListNode 頭；    
// 創(chuàng)建鏈表節(jié)點的類  
// 鏈表的一個節(jié)點獲取兩個東西：一個是節(jié)點的值  
// other 是指向另一個節(jié)點的指針  
靜態(tài)類 LinkedListNode    
{   
整 數(shù)值；   
接下來是LinkedListNode；   
// 類 LinkedListNode 的構造函數(shù)  
LinkedListNode（整數(shù) 編號）  
{  
瓦爾=沒有；  
下一個= 空；  
}  
}    
// 反轉鏈表的方法  
LinkedListNode reverse(LinkedListNode節(jié)點)  
{  
// 進行初始化   
// 按照定義的步驟   
LinkedListNode 前一個 =  null ;  
LinkedListNode 當前 = 節(jié)點；  
LinkedListNode next =  null ;      
while  (curr !=  null )   
{  
next = curr.next;  
當前.下一個=上一個；  
以前的=當前；  
當前=下一個；  
}  
節(jié)點=前一個；  
返回 節(jié)點；  
}    
//顯示鏈表的內(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 的對象  
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( "反轉前的鏈表為：" );  
listObj.printList（頭）；  
head = listObj.reverse(head);  
System.out.println( "\n" );  
System.out.println( "反轉后鏈表為：" );  
listObj.printList（頭）；  
}  
}  

輸出：

反轉前的鏈表為：
4 6 7 1 5 8 3 2
反轉后鏈表為：
2 3 8 5 1 7 6 4

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

使用遞歸方法反轉鏈表

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

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

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

第 3 步：將其余部分加入第一個。

第四步：固定頭指針。

執(zhí)行

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

文件名： LinkedListRecursive.java

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

輸出：

反轉前的鏈表為：
4 6 7 1 5 8 3 2
反轉后鏈表為：
2 3 8 5 1 7 6 4

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

使用堆棧反轉鏈表

下面是使用棧對鏈表進行反轉時使用的步驟。

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

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

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

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

執(zhí)行

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

文件名： LinkedListStack.java

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

輸出：

反轉前的鏈表為：
4 6 7 1 5 8 3 2
反轉后鏈表為：
2 3 8 5 1 7 6 4

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

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

以下是使用數(shù)組對鏈表進行反轉時使用的步驟。

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

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

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

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

執(zhí)行

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

文件名： LinkedListArray.java

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

輸出：

反轉前的鏈表為：
4 6 7 1 5 8 3 2
反轉后鏈表為：
2 3 8 5 1 7 6 4

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