Programming Skills: Reverse Link List

[題目]
Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

https://leetcode.com/problems/reverse-linked-list/description/

把link list反轉，例如1->2->3->4變成4->3->2->1

[思路1]

這個方法是 : 每次都把pointer tail的下一個node插到最前頭

D(prev)->1(tail)->2->3->4

D(prev)->2->1(tail)->3->4

D(prev)->3->2->1(tail)->4

D(prev)->4->3->2->1(tail)

-----

class Solution {

public:

ListNode* reverseList(ListNode* head) {

ListNode d(0,head);

ListNode *tail = head, *prev=&d;

while(tail && tail->next)

{

ListNode *tmp=prev->next;

prev->next = tail->next;

tail->next = tail->next->next;

prev->next->next = tmp;

}

return prev->next;

}

};

[思路2]
我們可以把list分成，反轉完/還沒反轉完，兩個部分。
然後每次都從"還沒反轉完的list"把head node抓出來，插入"已經反轉完的list"的頭部。
e.g.
反轉完list/尚未反轉完list
{D->} / {1(cur)->2->3->4}
{D->1}/ {2(cur)->3->4}

{D->2->1}/ {3(cur)->4}

{D->3->2->1}/ {4(cur)}

{D->4->3->2->1}/ {}

所以簡單地說你先準備一個new list ，然後把old list中的node一個個插入往new list的head。


/**
 * 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) {
        ListNode D(-1);
        D.next = NULL;
        ListNode* cur=head;

        while(cur){
        ListNode* tmp=cur->next;
        cur->next = D. next;
        D.next = cur;
        cur = tmp;
        }
        return D.next;
    }
};