[Leetcode]Reverse Linked List-再書き込みシングルチェーンテーブル反転
1610 ワード
Leetcodeはたまたままたこの問題が発生しました.面接アルゴリズムはよくある問題型のようですが、長い間書いたことがありません.今回は書くのに時間がかかりました.
主に思想の選択に遅れている.
1つは、遍歴時にポインタを直接反転させることで効率的ですが、前後のポインタと後続の関係をうまく処理する必要があります.
第二に、新しいチェーンヘッダーを構築し、遍歴時にチェーン要素を直接新しいリンクに追加することで、このアルゴリズムは比較的簡明である.
3つ目は、チェーンテーブルを最後から2番目のビット要素に再帰的に巡回し、nextポインタを順次反転することです.
主に思想の選択に遅れている.
1つは、遍歴時にポインタを直接反転させることで効率的ですが、前後のポインタと後続の関係をうまく処理する必要があります.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *pre = NULL;
struct ListNode *p = head;
while(p)
{
struct ListNode *tmpNext = p->next;//current next node
p->next = pre;
pre = p;
p = tmpNext;
}
return pre;
}
第二に、新しいチェーンヘッダーを構築し、遍歴時にチェーン要素を直接新しいリンクに追加することで、このアルゴリズムは比較的簡明である.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode newListHead = {
0, NULL
};
struct ListNode *p = head;//first node
while(p)
{
struct ListNode *tmpnew = newListHead.next;
struct ListNode *tmp = p->next;
newListHead.next = p;
p->next = tmpnew;
p = tmp;
}
return newListHead.next;
}
3つ目は、チェーンテーブルを最後から2番目のビット要素に再帰的に巡回し、nextポインタを順次反転することです.
/**
* 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* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
この方法はleetcodeから見たものであり、スタックの操作に類似しており、一定の啓発性がある.