LeetCode206
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
206.png
这里我使用的是类似与链表的头插法
#include <iostream>
#include <cstdio>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/*迭代法*/
ListNode *createList()
{
ListNode *pHead = NULL;
ListNode *p = pHead;
char x;
while(cin>>x)
{
if(x == 'q')
{
break;
}
int value = x - '0';
ListNode *pNew = new ListNode(value);
pNew->next = NULL;
if(pHead == NULL)
{
pHead = pNew;
}
else
{
p->next = pNew;
}
p = pNew;
}
return pHead;
}
void displayList(ListNode *head)
{
ListNode *p = head;
while(p != NULL)
{
cout<<p->val<<"->";
p = p->next;
}
cout<<"NULL"<<endl;
}
ListNode* reverseList(ListNode* head) {
ListNode *rhead = NULL;
ListNode *p = rhead;
ListNode *q = head;
while(q != NULL)
{
int value = q->val;
ListNode *pNew = new ListNode(value);
pNew->next = NULL;
if(rhead == NULL)
{
rhead = pNew;
}
else
{
pNew->next = rhead;
rhead = pNew;
}
q = q->next;
}
return rhead;
}
/*递归法*/
ListNode* reverseList2(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode *p = reverseList2(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};
int main()
{
Solution s;
ListNode *head,*reverse;
head = s.createList();
s.displayList(head);
reverse = s.reverseList(head);
s.displayList(reverse);
return 0;
}
LeetCode92
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
92.png
链表反转示意图
方法一关键代码：
第一步
prev->next = curr->next
第二步
curr->next = head2->next
第三步
head2->next = curr
第四步
curr = prev->next
initial.png
第一次循环1.png
第一次循环2.png
第一次循环3.png
第一次循环4.png
第一次循环结束调整.png
第二次循环1.png
第二次循环4.png
第二次循环结束.png
ListNode* reverseBetween(ListNode* head, int m, int n)
{
if (head == NULL) {
return NULL;
}
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *iter = dummy;
for (int i = 0; i < m - 1; i++) {
iter = iter->next;
}
ListNode *prev = iter->next;
ListNode *curr = prev->next;
for (int i = 0; i < n - m; i++) {
prev->next = curr->next;
curr->next = iter->next;
iter->next = curr;
curr = prev->next;
}
return dummy->next;
}
方法二关键代码：
(没什么关键代码)就是非常直观的思路
取出链表中需要反转的部分，单独反转，然后在和别的正常部分接在一起。
需要注意的就是链表只有一个数时的反转。
果然自己头脑太简单，只能用巨多的if-else来补充了。。
虽然两种方法提交都没什么差别
测试用例
1->2->3->4->5 , m=2, n=4
5 , m=1, n=1
ListNode* reverseBetween(ListNode* head, int m, int n)
{
int length = 0;
ListNode *point = head;
ListNode *L1 = NULL;
ListNode *L2 = NULL;
ListNode *L3 = NULL;
ListNode *reverse_b;
ListNode *p,*q,*r;
p = L1;
q = L2;
r = L3;
while (point != NULL)
{
int value = point->val;
ListNode *New = new ListNode(value);
New->next = NULL;
length ++;
if(length>0 && length<m)
{
if(L1 == NULL)
{
L1 = New;
}
else
{
p->next = New;
}
p = New;
}
else if (length>=m && length<=n)
{
if(L2 == NULL)
{
L2 = New;
q = New;
}
else
{
New->next = L2;
L2 = New;
}
}
else
{
if(L3 == NULL)
{
L3 = New;
}
else
{
r->next = New;
}
r = New;
}
point = point->next;
}
if(L1 == NULL)
{
if(L2 == NULL)
{
if(L3 == NULL)
{
reverse_b = reverse_b;
}
else
{
reverse_b = L3;
}
}
else // L2!=NULL
{
if(L3 == NULL)
{
reverse_b = L2;
}
else //L3!=NULL
{
reverse_b = L2;
q->next = L3;
}
}
}
else //L1!=NULL
{
if(L2 == NULL)
{
if(L3 == NULL)
{
reverse_b = L1;
}
else //L3!=NULL
{
reverse_b = L1;
p->next = L3;
}
}
else // L2!=NULL
{
if(L3 == NULL)
{
reverse_b = L1;
p->next = L2;
}
else //L3!=NULL
{
reverse_b = L1;
p->next = L2;
q->next = L3;
}
}
}
return reverse_b;
}
