## 25 Reverse Nodes in K Group 每k个一组翻转链表

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed.

## 24. Swap Nodes in Pairs 成对交换节点

Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. Difficulty: Medium 解法1 迭代.建立dummy结点(注意之后释放该结点),拿1,2,3,4举例,第一次循环pre=dummy,将1指向3,将2指向1,再将pre设为1 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *dummy = new ListNode(-1),*pre = dummy; dummy->next = head; while (pre->next && pre->next->next) { // t=2 ListNode* t = pre->next->next; // 1 ->(指向next) 3 pre->next->next = t->next; // 2 -> 1 t->next = pre->next; // pre(dummy) -> t pre->next = t; // pre = 1 pre = t->next; //所以第一次while循环后的结果为 //dummy-> t(2) -> 1 -> 3 //pre = 1 然后到下一次循环 } ListNode* res = dummy->next; delete dummy; dummy = NULL; return res; } }; 解法2 递归,先递归到最后两个进行交换,再依次向前迭代.

## 23. Merge K Sorted Lists 合并k个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Difficulty: Hard 合并k个排序列表.是前面21. Merge Two Sorted Lists 混合插入有序链表的升级版. 解法1 最先想到的就是利用21. Merge Two Sorted Lists 混合插入有序链表拿第一个链表与第二个合并,合并结果在于第三个比较.这样需要合并k-1次才能完成. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int n = lists.

## 21. Merge Two Sorted Lists 混合插入有序链表

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 Difficulty: Easy 这道题让我们把两个有序的链表合并成一个有序的链表,与剑指offer 16题完全相同. 解法1 按照剑指offer 16题的递归解法 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1==NULL) return l2; if (l2==NULL) return l1; ListNode* head = NULL; if (l1->val<l2->val) { head = l1; head->next = mergeTwoLists(l1->next,l2); } else { head = l2; head->next = mergeTwoLists(l2->next,l1); } return head; } }; 解法2 采用循环的方式

## 19. Remove Nth Node From End of List 移除链表倒数第N个节点

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. Difficulty: Medium 这道题让我们溢出链表中第N个节点,并制定n为有效的,就是n不会大于链表元素的总个数.看网上说这道题在问的时候可能会加上限制在一次循环的条件完成.如果用一次循环完成的话,就不能单独用一次循环来求链表元素的个数,要在循环到要删除的元素的位置时就该删除该元素.所以需要一点技巧. 我们可以定义两个指针pre,cur.先让cur前进N步,如果此时cur指向的为NULL,说明该链表的长度为N,所以移除首个元素就可以.如果cur指向的不为NULL,那么此时同时让pre,cur同时前进,直到cur指向最后一个元素,此时pre指向的就是倒数第N个元素,删除即可. 剑指offer 56题与这道题稍微有点像,可以一起看下 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (!