【链表】 206. 反转链表

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* reverseList(ListNode* head) {
12         ListNode *p1;
13         ListNode *p2;
14         ListNode *p3;
15 
16         // 链表为空, 或者单节点链表直接返回头部
17         if (NULL == head || NULL == head->next)
18         {
19             return head;
20         }
21 
22         p1 = head;
23         p2 = head->next;
24 
25         while (p2 != NULL)
26         {
27             p3 = p2->next;
28             p2->next = p1;
29             p1 = p2;
30             p2 = p3;
31         }
32 
33         head->next = NULL;
34         head = p1;
35 
36         return head;
37     }
38 };

 1 //递归
 2 Node *reverseTraveral(Node *head, Node *pre)
 3 {
 4        Node *p = head->next;
 5        head->next = pre;
 6        if(p)
 7      {
 8               return reverseTraveral(p, head);
 9      }
10        else
11      {
12               return head;
13      }
14 }