文章目錄
- 前言
- 題目
- 題解
- No1：雙指針法
- NO2：遞歸解法
- 參考資料
前言
哈喽，我是長路，目前剛剛大三，方向是後端也偶爾搗鼓下前端，現在的主語言是Java。之前一大段時間都是在學習web開發的一些技術，就很久沒有進行類似于資料結構、算法之類的學習與刷題，打算這段時間拾起來好好學一學、搞一搞。
這段時間也是機緣巧合看到草帽路飛的部落格，加了自學群，正巧看到部落客組織在群裡組織了leetcode刷題打卡活動，我也就參與進來，為期一個月，打算堅持每天都花一些時間做一些題目，并通過部落格的方式來進行記錄。
目前跟着一個Github倉庫刷題(leetcode)：代碼随想錄leetcode刷題，目前為連結清單專題。
題目
題目來源leetcode
leetcode位址：206. 反轉連結清單，難度：簡單。
題目描述(摘自leetcode)：
給你單連結清單的頭節點 head ，請你反轉連結清單，并傳回反轉後的連結清單。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
本地調試代碼：
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
//業務代碼
public ListNode reverseList(ListNode head){
...
}
public static void main(String[] args) {
ListNode node7 = new ListNode(7, null);
ListNode node6 = new ListNode(6, node7);
ListNode node5 = new ListNode(5, node6);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
//反轉連結清單
ListNode listNode = new Solution().reverseList(node1);
//周遊
printList(listNode);
}
private static void printList(ListNode listNode) {
if(listNode == null){
return;
}
System.out.print("[");
while(listNode != null){
System.out.print(listNode.val);
if(listNode.next != null){
System.out.print(",");
}
listNode = listNode.next;
}
System.out.print("]");
}
}
題解
思路：定義前置指針及目前指針，周遊連結清單每個節點時移動前置、目前指針，周遊到某個節點時首先使用臨時變量存儲目前指針的next，緊接着進行反轉操作将目前指針指向節點的next指向前置指針，接着兩個指針統一往後移即可。
代碼：
/**
* 雙指針法
* @param head
* @return
*/
public ListNode reverseList(ListNode head){
//head為null或一個時
if(head == null || head.next == null){
return head;
}
//定義兩個指針
ListNode temp;
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
temp = cur.next;
cur.next = pre;
//指針移動，各自向後移動
pre = cur;
cur = temp;
}
return pre;
}
思路：當有重複相同的動作時你就可以使用到遞歸，這裡反轉連結清單實際上就有大量相同的反轉操作。遞歸方法參數定義兩個，一個是前置指針指向的節點、第二個是目前指針，将目前指針為null情況作為出口傳回反轉連結清單後的頭節點也就是參數中的前置指針。每個重複方法中的核心操作就是：
cur.next = pre;
。
/**
* 遞歸
* @param head
* @return
*/
public ListNode reverseList(ListNode head){
return reverse(null,head);
}
/**
* 反轉，其實也就是周遊了一遍
* @param pre
* @param cur
* @return 原始連結清單最後一個節點
*/
private ListNode reverse(ListNode pre, ListNode cur) {
//遞歸終止條件
if(cur == null){
return pre;
}
//提前儲存下一個節點
ListNode temp = cur.next;
//進行連結清單中某個節點next指向反轉
cur.next = pre;
return reverse(cur,temp);
}
參考資料
[1]. leetcode題解
[2]. 代碼随想錄leetcode刷題—反轉連結清單