剑指OFFER 22.反转链表

剑指OFFER 22.反转链表

• 22.反转链表

• 定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

  思考题：

  • 请同时实现迭代版本和递归版本。

    样例

    输入:1->2->3->4->5->NULL
    
    输出:5->4->3->2->1->NULL

/**
 * 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* pre = nullptr;
        auto cur = head;
        while(cur)
        {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }  
        return pre;
    }
};

// 迭代做法
  // Iterative C++ program to reverse 
  // a linked list 
  #include <iostream> 
  using namespace std; 

  /* Link list node */
  struct Node { 
      int data; 
      struct Node* next; 
      Node(int data) 
      { 
          this->data = data; 
          next = NULL; 
      } 
  }; 

  struct LinkedList { 
      Node* head; 
      LinkedList() 
      { 
          head = NULL; 
      } 

      /* Function to reverse the linked list */
      void reverse() 
      { 
          // Initialize current, previous and 
          // next pointers 
          Node* current = head; 
          Node *prev = NULL, *next = NULL; 

          while (current != NULL) { 
              // Store next 
              next = current->next; 

              // Reverse current node's pointer 
              current->next = prev; 

              // Move pointers one position ahead. 
              prev = current; 
              current = next; 
          } 
          head = prev; 
      } 

      /* Function to print linked list */
      void print() 
      { 
          struct Node* temp = head; 
          while (temp != NULL) { 
              cout << temp->data << " "; 
              temp = temp->next; 
          } 
      } 

      void push(int data) 
      { 
          Node* temp = new Node(data); 
          temp->next = head; 
          head = temp; 
      } 
  }; 

  /* Driver program to test above function*/
  int main() 
  { 
      /* Start with the empty list */
      LinkedList ll; 
      ll.push(20); 
      ll.push(4); 
      ll.push(15); 
      ll.push(85); 

      cout << "Given linked list\n"; 
      ll.print(); 

      ll.reverse(); 

      cout << "\nReversed Linked list \n"; 
      ll.print(); 
      return 0; 
  }