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

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.

//
//
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);
}

最后

以上就是独特康乃馨为你收集整理的C实现 LeetCode->Reverse Linked List II （双指针大法）(单链表反转)的全部内容，希望文章能够帮你解决C实现 LeetCode->Reverse Linked List II （双指针大法）(单链表反转)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。