链表翻转

#链表翻转

给定一个链表 >1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

实现算法把链表从第 m = 2 位到第 n = 6 位之间的数字进行反转，变成：

1 -> 6 -> 5 -> 4 -> 3 -> 2 -> 7 -> 8 -> 9

实现的过程中不可以申请新的内存地址，时间复杂度是 Θ(n)。

首先是让链表空转 m - 1 位，设定 pHead = 2, 然后让 pPre = 3，也就是会变成最后一位的数字。pCur = 4，这是马上要变成 pHead 下一位的数字。完成 pCur 和 pPre 位置的变换，然后让 pCur 变成一下位，直到 n = 6。过程图如下：

下面是实现的代码：

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 #include <stdlib.h>
#include <stdio.h>

typedef struct tagSNode{
  int value;
  struct tagSNode *pNext;
}SNode;

SNode* create(value){
  SNode *node = malloc(sizeof(SNode));
  node->value=value;
  node->pNext=NULL;
  return node;
}

void print(SNode *list){
  while(list){
    printf("%i\n", list->value);
    list = list->pNext;
  }
}

void rotate(SNode *pHead, int m, int n){
  SNode *pCur = pHead->pNext;
  int i = 0;
  for(;i<m-1;i++){
    printf("index is%i\n", i);
    pHead = pCur;
    pCur = pCur->pNext;
  }

  SNode *pPre = pCur;
  pCur = pCur->pNext;

  n--;
  SNode *pNext;
  for(;i<n;i++){
    pNext = pCur->pNext;
    pCur->pNext = pHead->pNext;
    pHead->pNext = pCur;
    pPre->pNext=pNext;
    pCur=pNext;
  }
}

// given 1→2→3→4→5, m=2,n=4, return 1→4→3→2→5
int main(){
  int m = 3;
  int n = 6;

  SNode *list = create(0);
  SNode *tail = list;
  for(int i=1;i<9;i++){
    tail->pNext = create(i);
    tail = tail->pNext;   
  }

  print(list);
  rotate(list,m,n);
  print(list);
}