【第一部分】04Leetcode刷题

一、反转链表 II

 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* reverseBetween(ListNode* head, int m, int n) 
12     {
13          if (!head || !head->next) 
14             return head;
15         
16         ListNode* dummy = new ListNode(0);
17         dummy->next = head;
18         
19         ListNode* prev = dummy;
20         for (int i = 0; i < m - 1; i++) 
21             prev = prev->next;
22         ListNode* start = prev->next;
23         ListNode* then = start->next;
24         
25         for (int i = 0; i < n - m; i++) 
26         {
27             start->next = then->next;
28             then->next = prev->next;
29             prev->next = then;
30             then = start->next;
31         }        
32         return dummy->next;
33     }
34 };

二、回文链表

【题目】234. 回文链表

 1 class Solution {
 2 public:
 3     bool isPalindrome(ListNode* head) 
 4     {
 5         if (!head || !head->next) return true;
 6         ListNode *slow = head, *fast = head;
 7         while (fast->next && fast->next->next) //找到中点
 8         {
 9             slow = slow->next;
10             fast = fast->next->next;
11         }
12         ListNode *last = slow->next, *pre = head;
13         while (last->next)  //反转
14         {
15             ListNode *tmp = last->next;
16             last->next = tmp->next;
17             tmp->next = slow->next;
18             slow->next = tmp;
19         }
20         while (slow->next) //比较
21         {
22             slow = slow->next;
23             if (pre->val != slow->val) 
24                 return false;
25             pre = pre->next;
26         }
27         return true;
28     }
29 };

三、两两交换链表中的节点

【题目】24. 两两交换链表中的节点

C++ Soution 1:

 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* swapPairs(ListNode* head) 
12     {
13         if (!head || !head->next) return head;
14         ListNode *t = head->next;
15         head->next = swapPairs(head->next->next);
16         t->next = head;
17         return t;
18     }
19 };

C++ Soution 2:

 1 class Solution {
 2 public:
 3     ListNode* swapPairs(ListNode* head) 
 4     {
 5         ListNode *dummy = new ListNode(-1), *pre = dummy;
 6         dummy->next = head;
 7         while (pre->next && pre->next->next) 
 8         {
 9             ListNode *t = pre->next->next;
10             pre->next->next = t->next;
11             t->next = pre->next;
12             pre->next = t;
13             pre = t->next;
14         }
15         return dummy->next;
16     }
17 };