単方向連結リストの各ノード（node）は構造体ポインタであり、以下を含みます：
- ノードの要素データ；
- 次のノードのポインタアドレス。
LeetCodeにおける連結リストの表現方法：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};leetcode206. 連結リストの反転#
反復法#
ListNode* reverseList(ListNode* head) {
ListNode *head_prev = nullptr, *head_next;
while (head) {
head_next = head->next;
head->next = head_prev;
head_prev = head;
head = head_next;
}
return head_prev;
}- 時間計算量：O(n)
- 空間計算量：O(1)
再帰法#
ListNode* reverseList(ListNode* head, ListNode* head_prev = nullptr) {
if (head == nullptr) {
return head_prev;
}
ListNode* head_next = head->next;
head->next = head_prev;
return reverseList(head_next, head);
}- 時間計算量：O(n)
- 空間計算量：O(n)
return reverseList(head_next, head);
- これは末尾再帰形式です。 #末尾再帰 #再帰
- 「次に処理するノード」(head_next) を新しい
headとして渡します。 - 「現在のノード」(head) を次回の再帰の
head_prevとして渡します。
ノート
反復法では、ListNode *head_prev = nullptr は関数内部にあります。再帰法では、ListNode *head_prev = nullptr は関数の引数内にあります。
・反復法：今回の関数呼び出し内でのみ存在し、呼び出しは一度きりです。
・再帰法：各再帰レベル（各関数呼び出し）がそれぞれの head_prev を持ちます。
leetcode234. 回文連結リスト#
快慢ポインタ法（速いポインタと遅いポインタ）#
反転リストの問題を解いた直後だったので、連結リストの後半部分を反転させ、前半部分と後半部分が同じかどうかを比較する方法を思いつきました。連結リストを配列に格納してから回文比較を行う方がコード量は少なくなりますが、快慢ポインタ法の利点は明らかです：O(n) の追加空間（メモリ）を避けることができます。
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return true;
}
ListNode* head1=head; // head1: 遅いポインタ
ListNode* head2=head; // head2: 速いポインタ
while(head2!=nullptr&&head2->next!=nullptr){
head1=head1->next;
head2=head2->next->next;
}
ListNode* secondHalf=reverseList(head1,nullptr);
ListNode* p1=head;
ListNode* p2=secondHalf;
bool flag=true;
while(p2!=nullptr){
if(p1->val!=p2->val){
flag=false;
break;
}
p1=p1->next;
p2=p2->next;
}
return flag;
}
ListNode* reverseList(ListNode* head,ListNode *head_prev = nullptr) {
ListNode *head_next;
if(head==nullptr){
return head_prev;
}
head_next=head->next;
head->next=head_prev;
return reverseList(head_next,head);
}