Linked List

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 (!

Add TwoNumbers 两个链表相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.