文章目錄
- （1）題目描述
- （2）解題思路
- 1）解法1：調整節點指標的方向
- 2）解法2：頭插法
題目難度：《簡單》
（1）題目描述
給你單鏈表的頭節點
head，請你反轉鏈表，并回傳反轉后的鏈表，
示例1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例2：
輸入：head = [1,2]
輸出：[2,1]
示例3：
輸入：head = [ ]
輸出：[ ]
LeetCode鏈接：206. 反轉鏈表
（2）解題思路
1）解法1：調整節點指標的方向
- 步驟
- 定義一個指標 cur，用來遍歷鏈表
- 定義一個指標 prev，保存 cur 的上一個節點的位置，初始指向 NULL
- 定義一個指標 next，保存 cur 的下一個節點的位置，用來迭代
- 通過 prev 和 cur 來調整每個節點指標的方向，next 進行迭代
- 最后回傳頭節點指標 head 即可
- 代碼如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//解題思路：把鏈表中所有節點的next指標指向反轉
struct ListNode* prev = NULL; //保存cur的上一個節點的位置
struct ListNode* cur = head; //遍歷鏈表
while(cur != NULL)
{
struct ListNode* next = cur->next; //保存cur的下一個節點位置
cur->next = prev; //調整當前節點next指標的方向
prev = cur;
cur = next;
}
head = prev; //更新頭節點
return head;
}
2）解法2：頭插法
- 然后把鏈表中的所有節點依次頭插到一個新鏈表中，相當于反轉了原鏈表
- 定義一個指標 cur，用來遍歷原鏈表
- 定義一個指標 next，保存 cur 的下一個節點的位置
- 定義一個指標 newhead，指向新鏈表的頭節點
- 動圖演示
- 代碼如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//解題思路：把鏈表中的所有節點依次頭插到一個新鏈表中，相當于反轉了原鏈表
//當鏈表為慷訓鏈表只有一個節點時
if(head == NULL || head->next == NULL)
{
return head;
}
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur)
{
//保存cur當前所在節點的下一個節點的位置
struct ListNode* next = cur->next;
cur->next = newhead; //開始頭插
newhead = cur; //更新頭節點
cur = next; //cur指向下一個待插入的節點
}
return newhead;
}
大家快去動手練習一下吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297140.html
標籤：其他