C实现 LeetCode->Reverse Linked List II （双指针大法）(单链表反转)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//
//
ReverseLinkedListII.c
//
Algorithms
//
//
Created by TTc on 15/6/22.
//
Copyright (c) 2015年 TTc. All rights reserved.
//
/**
*
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.
只要用跟编号ReverseNodesInk-Group一模一样的Reverse()函数就可以了。
当然这题要用递归做也可以。
*/
#include "ReverseLinkedListII.h"
#include <stdlib.h>
#include <string.h>
#include "List.h"
/********************************************************************/
// LeetCode 答案
/********************************************************************/
struct ListNode {
int val;
struct ListNode *next;
};
//双指针大法
/*Since only constant memory is allowed, time cost is O(k) */
static struct ListNode*
Reverse(struct ListNode *begin, struct ListNode *end){
struct ListNode* prev = begin->next;
struct ListNode* curr = prev->next;
while(curr != end){
prev->next = curr->next;
curr->next = begin->next;
begin->next = curr;
curr = prev->next;
}
return prev;
}
struct ListNode*
reverseBetween(struct ListNode* head, int m, int n) {
if(head == NULL) return head;
struct ListNode *dummyHead = (struct ListNode *)malloc(sizeof(*dummyHead));
dummyHead->next = head;
struct ListNode *iter = head;
struct ListNode *prev = dummyHead;
struct ListNode *curr = head;
int count = 1;
while(iter->next != NULL){
if(count < m) prev = prev->next;
if(count < n) curr = curr->next;
iter = iter->next;
++count;
}
Reverse(prev, curr->next);
return dummyHead->next;
}
/********************************************************************/
/********************************************************************/
/********************************************************************/
// List.c 是范性类 单链表
/********************************************************************/
//反转单链表中
begin
到 end 节点
static ListElmt*
tt_Reverse(ListElmt *begin, ListElmt *end){
ListElmt* prev = begin->next;
ListElmt* curr = prev->next;
while(curr != end){
prev->next = curr->next;
curr->next = begin->next;
begin->next = curr;
curr = prev->next;
}
return prev;
}
ListElmt*
tt_reverseBetween(ListElmt* head, int m, int n) {
if(head == NULL) return head;
ListElmt *dummyHead = (ListElmt *)malloc(sizeof(*dummyHead));
dummyHead->next = head;
ListElmt *iter = head;
ListElmt *prev = dummyHead;
ListElmt *curr = head;
int count = 1;
while(iter->next != NULL){
if(count < m) prev = prev->next;
if(count < n) curr = curr->next;
iter = iter->next;
++count;
}
tt_Reverse(prev, curr->next);
return dummyHead->next;
}
void
test_reverseBetween(){
List l1;
list_init(&l1, free);
int *data ;
int array[15] = {100,200,300,400,500,600,700,800,900,1000};
for (int i = 0; i< 10; i++) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return ;
*data = array[i];
if (list_ins_next(&l1, NULL, data) != 0)
//逐个插入元素
return;
}
print_list(&l1);
ListElmt *result = tt_reverseBetween(list_head(&l1),0,10);
printf("result->val===%dn",*(int *)result->data);
print_listNode(result);
}