链表划分

#链表划分

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

和一个对比数 value = 4, 实现算法把链表划分为大于 4 的部分和小于等于 4 的部分，然后合并起来变成如下：

1 -> 2 -> 4 -> 3 -> 9 -> 5

题目不难，关键在于熟悉链表的 next 指针。首先定义两个指针，left 和 right，分别用来指向大于 value 的值和小于等于 value 的值。对原链表进行遍历，过程图如下：

这里定义了 leftHead = 0, rightHead = 0，是为了方便书写代码，在最后组合结果的时候会去掉 0。

下面是实现的代码：

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 #include <stdlib.h>
#include <time.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 split(SNode *list, int size, int v){
  SNode *p = list->pNext;
  SNode *leftHead = create(0);
  SNode *rightHead = create(0);

  SNode *left = leftHead;
  SNode *right = rightHead;

  while(p!=NULL){
    if(p->value > v){
      right->pNext=p;
      right = p;
    }else{
      left->pNext=p;
      left=p; 
    }
    p=p->pNext;
  }
    left->pNext = rightHead->pNext;
    right->pNext=NULL;
    list->pNext=leftHead->pNext;
}

int main(){
  SNode *list = create(0);
  SNode *node1 = create(1);
  SNode *node2 = create(5);
  SNode *node3 = create(7);
  SNode *node4 = create(8);
  SNode *node5 = create(2);
  SNode *node6 = create(9);
  list->pNext = node1;
  node1->pNext = node2;
  node2->pNext = node3;
  node3->pNext = node4;
  node4->pNext = node5;
  node5->pNext = node6;

  int v = 4;
  print(list);
  split(list, 7, 4);
  puts("after reorder");
  print(list);
  return 0;
}