一.Reverse Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *p=head,*newHead=NULL,*next=NULL;
while(p){
next = p->next;
p->next = newHead;
newHead = p;
p = next;
}
return newHead;
}
};
Next challenges: (M) Reverse Linked List II (M) Binary Tree Upside Down
Reverse Linked List II
Total Accepted: 58179 Total Submissions: 218404 Difficulty: Medium
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode *head)
{
ListNode* p = head,*newHead = NULL,*next = NULL;
while(p){
next = p->next;
p->next = newHead;
newHead = p;
p = next;
}
return newHead;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m==n){
return head;
}
ListNode *m_pre=NULL,*n_next=NULL,*tail=NULL,*cur=head;
int cnt = ;
while(cur){//找m的前驱
++cnt;
if(cnt == m){
tail = cur;//反转之前的头，反转之后的尾
break;
}
m_pre = cur;
cur=cur->next;
}
while(cur){//找n的后继
n_next = cur->next;
if(cnt == n){
break;
}
cur = n_next;
++cnt;
}
if(cur){
cur->next = NULL;
}
ListNode *newHead = reverseList(tail);
if(m_pre){
m_pre->next = newHead;
}else{
head = newHead==NULL? head:newHead;
}
if(tail){
tail->next = n_next;
}
return head;
}
};