Reverse a singly linked list

反轉一個單向鏈結串列
e.g.
input: 1 -> 2 -> 3 -> 4 -> 5
output: 5 -> 4 -> 3 -> 2 -> 1

Method 1:  iterative version
令一個空的head pointer叫做newHead, 將原linked list從頭掃到尾一次, 依序將掃到的結點加入newHead指向的linked list, 其中必須用一個temp pointer紀錄下一個要加入的結點, 且將原head前進

1. temp = OldHead
2. Advance OldHead
3. Add temp to newHead list:     temp->next = newHead
4. Update newHead:     newHead = temp
5. repeat 1.~4. until OldHead pointer to NULL pointer
6. return newHead

Method 2: Recursive version

• Where is the sub-problem?

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Sub-problem: 2 -> 3 -> 4 -> 5 -> NULL

Idea 1

1. Recursively reverse the sub-problem

2. the sub-problem part will return a pointer R points to the end of reversed linked list

3. Make R point the previous node P ( need another pointer P to keep tracking the previous node)

4. return P as the recursive part's result

5. Base case: current pointer points to NULL, change the head pointer to P

缺點：

1. 需要兩個參數，一個記錄當前子問題的頭，一個紀錄前一個Node

2. head之更改必須寫死在Base case中

3. 必須回傳reverse結果的尾結點

Idea 2

1. Recursively reverse the sub-problem

2. Base case: current node's next node is NULL, change the head pointer to current node

3. current node's next' next pointer point to current node

4. current node's next point to NULL

缺點：

1. head之更改必須寫死在Base case中

C++ code:

#include <iostream> using namespace std; class Node{ public: Node( ) : value(0), next(NULL){} Node( int theValue, Node* nextNode ) : value(theValue), next(nextNode){} int value; Node* next; }; class LinkedList{ public: LinkedList( ); ~LinkedList( ); void AddToEnd( int theValue ); void AddToFront( int theValue ); void DeleteFront( ); void ShowElements( ) const; void Reverse( ); // iterative void RecursiveReverseComplex( ); // two parameter void RecursiveReverseSimple( ); // one parameter private: Node* head; Node* recurReverseComplex( Node*, Node* ); // for RecursiveReverseComplex void recurReverseSimple( Node* ); // for RecursiveReverseSimple }; LinkedList::LinkedList( ): head(NULL){ } LinkedList::~LinkedList( ){ while( head != NULL ) DeleteFront(); } void LinkedList::AddToEnd( int theValue ){ Node *current = head; // empty List if( current == NULL ){ AddToFront( theValue ); return; } // Non-empty list while( current->next != NULL ) current = current->next; Node *newNode = new Node(theValue, NULL); current->next = newNode; } void LinkedList::AddToFront( int theValue ){ Node *newNode = new Node(theValue, head); head = newNode; } void LinkedList::DeleteFront( ){ if( head == NULL ) return; Node *headNext = head->next; delete head; head = headNext; } void LinkedList::ShowElements( ) const{ Node *current = head; while( current != NULL ){ cout << current->value << " "; current = current->next; } cout << endl; } void LinkedList::Reverse( ){ if( head == NULL ) return; Node *current = head; Node *newHead = NULL; while( current != NULL ){ Node *temp = current; current = current->next; temp->next = newHead; newHead = temp; } head = newHead; } void LinkedList::RecursiveReverseComplex( ){ recurReverseComplex(head, NULL); } Node* LinkedList::recurReverseComplex( Node* current, Node* previous){ if( current == NULL ){ head = previous; return head; } Node *reversedEnd = recurReverseComplex(current->next, current); reversedEnd->next = previous; return previous; } void LinkedList::RecursiveReverseSimple( ){ recurReverseSimple( head ); } void LinkedList::recurReverseSimple( Node* current ){ if( current->next == NULL ) { head = current; return; } recurReverseSimple( current->next ); current->next->next = current; current->next = NULL; } int main( ){ LinkedList list; list.AddToEnd( 2 ); list.AddToEnd( 3 ); list.AddToEnd( 4 ); list.AddToEnd( 5 ); list.AddToFront( 1 ); list.AddToFront( 0 ); list.ShowElements( ); list.DeleteFront( ); list.ShowElements( ); list.Reverse( ); list.ShowElements( ); list.RecursiveReverseComplex( ); list.ShowElements( ); list.RecursiveReverseSimple( ); list.ShowElements( ); return 0; }