首页 > 代码库 > 61. Rotate List(M);19. Remove Nth Node From End of List(M)
61. Rotate List(M);19. Remove Nth Node From End of List(M)
61. Rotate List(M)
Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
- Total Accepted: 102574
- Total Submissions: 423333
- Difficulty: Medium
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 *rotateRight(ListNode *head, int k) { 12 if (head == nullptr || k == 0) return head; 13 int len = 1; 14 ListNode* p = head; 15 while (p->next) { // 16 len++; 17 p = p->next; 18 } 19 k = len - k % len; 20 p->next = head; // 21 for(int step = 0; step < k; step++) { 22 p = p->next; // 23 } 24 head = p->next; // 25 p->next = nullptr; // 26 return head; 27 } 28 };
16ms 19.35%
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 {// by guxuanqing@gmail.com 10 public: 11 ListNode* rotateRight(ListNode* head, int k) 12 { 13 if(NULL == head || NULL == head->next) return head;//null or one node 14 ListNode *p = NULL, *q = head; 15 int len = 1; 16 while (q->next)//cal the length of the list 17 { 18 ++len; 19 q = q->next; 20 } 21 q->next = head; 22 k %= len; 23 int tmp = len - k; 24 q = head; 25 while (--tmp) 26 { 27 q = q->next; 28 } 29 head = q->next; 30 q->next = NULL; 31 return head; 32 } 33 };
19. Remove Nth Node From End of List
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.
- Total Accepted: 169535
- Total Submissions: 517203
- Difficulty: Medium
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 *removeNthFromEnd(ListNode *head, int n) { 12 ListNode dummy(-1); 13 dummy.next = head; 14 ListNode *p = &dummy, *q = &dummy; 15 for (int i = 0; i < n; i++)//q先走n步 16 q = q->next; 17 while(q->next) { 18 p = p->next; 19 q = q->next; 20 } 21 ListNode *tmp = p->next; 22 p->next = p->next->next; 23 delete tmp; 24 return dummy.next; 25 } 26 };
6ms 64.75%
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 {// by guxuanqing@gmail.com 10 public: 11 ListNode* removeNthFromEnd(ListNode* head, int n) { 12 if(NULL == head || NULL == head->next) return NULL;//null or one node 13 ListNode dummy(-1); 14 dummy.next = head; 15 ListNode *p = &dummy, *q = &dummy; 16 int tmp = n; 17 while (tmp--) 18 { 19 q = q->next; 20 } 21 while (q->next) 22 { 23 q = q->next; 24 p = p->next; 25 } 26 ListNode *rnode = p->next; 27 p->next = rnode->next; 28 delete rnode; 29 return dummy.next; 30 } 31 };
9ms 23.47%
61. Rotate List(M);19. Remove Nth Node From End of List(M)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。