Given a list, rotate the list to the right by k places, where k is non-negative. For example:
Given ->->->->->NULL and k = ,
return ->->->->->NULL.
- Total Accepted: 102574
- Total Submissions: 423333
- Difficulty: Medium
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (head == nullptr || k == ) return head;
int len = ;
ListNode* p = head;
while (p->next) { //
len++;
p = p->next;
}
k = len - k % len;
p->next = head; //
for(int step = ; step < k; step++) {
p = p->next; //
}
head = p->next; //
p->next = nullptr; //
return head;
}
};
16ms 19.35%
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {// by guxuanqing@gmail.com
public:
ListNode* rotateRight(ListNode* head, int k)
{
if(NULL == head || NULL == head->next) return head;//null or one node
ListNode *p = NULL, *q = head;
int len = ;
while (q->next)//cal the length of the list
{
++len;
q = q->next;
}
q->next = head;
k %= len;
int tmp = len - k;
q = head;
while (--tmp)
{
q = q->next;
}
head = q->next;
q->next = NULL;
return head;
}
};
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: ->->->->, and n = . After removing the second node from the end, the linked list becomes ->->->.
Note:
Given n will always be valid.
Try to do this in one pass.
- Total Accepted: 169535
- Total Submissions: 517203
- Difficulty: Medium
/**
* 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) {
ListNode dummy(-);
dummy.next = head;
ListNode *p = &dummy, *q = &dummy;
for (int i = ; i < n; i++)//q先走n步
q = q->next;
while(q->next) {
p = p->next;
q = q->next;
}
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
return dummy.next;
}
};
6ms 64.75%
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {// by guxuanqing@gmail.com
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(NULL == head || NULL == head->next) return NULL;//null or one node
ListNode dummy(-);
dummy.next = head;
ListNode *p = &dummy, *q = &dummy;
int tmp = n;
while (tmp--)
{
q = q->next;
}
while (q->next)
{
q = q->next;
p = p->next;
}
ListNode *rnode = p->next;
p->next = rnode->next;
delete rnode;
return dummy.next;
}
};
9ms 23.47%