LeetCode 206——チェーンテーブルを反転
単一チェーンテーブルを反転するには反復法と再帰法の2種類がある.
1.反復法反復法は、チェーンテーブルを前後に巡回し、3つのポインタがそれぞれ隣接する3つのノードを指し、最初の2つのノードを反転させる、すなわち、2番目のノードが1番目のノードを指すように定義する.次にポインタを順番に後ろに移動し、2番目のノードが空になるまで終了し、チェーンテーブルのヘッダーを処理すればよい.
2.再帰法ベースライン条件:空のチェーンまたは1つのノードのみが、直接ヘッダポインタ に戻る.再帰条件:再帰呼び出し、サブチェーンテーブル反転後のヘッダポインタ を返す.
もっと素晴らしいものを手に入れて、「seniusen」に注目してください!
1.反復法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) // ,
{
return head;
}
else //
{
ListNode * p1 = head; //
ListNode * p2 = p1->next; //
ListNode * p3 = p2->next; //
while (p2) // , ,
{
p3 = p2->next;
p2->next = p1; // ,
p1 = p2; //
p2 = p3; //
}
head->next = NULL; // NULL
head = p1; //
return head;
}
}
};
2.再帰法
Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) // ,
{
return head;
}
else //
{
ListNode *new_head = reverseList(head->next); //
// head->next
//
head->next->next = head;
head->next = NULL;
return new_head;
}
}
};
もっと素晴らしいものを手に入れて、「seniusen」に注目してください!