爱喝茶的仙人掌

Try to write something.

线性表的链式表示 部分练习

Posted on Edited on In Views: Valine:
Symbols count in article: 15k Reading time ≈ 14 mins.
设计一个递归算法，删除不带头结点的单链表 L 中所有值为 x 的结点。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteRecursive(LNode &p, Elemtype x) {
  if (p == null) {
    return;
  }
  if (p->data == x) {
    LNode temp = p; 
    p = p->next; //在此处思考上层递归，会补链
    free(temp); 
    deleteRecursive(p, x);
  } else {
    deleteRecursive(p->next, x);
  }
}
在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述操作。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void deleteX(LinkList &L, Elemtype x) {
  while(L != null && L->next != null) {
    if (L->next->data == x) {
      LNode *temp = L->next;
      if (L->next->next != null) {
        L->next = L->next->next;
      } else {
        L->next = null;
      }
      free(temp);
    } else {
      L = L->next;
    }
  }
}
设 L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//从链表头部开始遍历，利用头插法生成新链表，再遍历输出新链表的值即可。
LinkList headInsert(LinkList &head, Elemtype value) {//该方法默认链表带有头节点
  temp = (LNode*)malloc(sizeof(LNode));
  temp->data = value;
  temp->next = head->next;
  head->next = temp;
}

void printReverse(LinkList L) {
  LNode current = L->next;
  Linklist reverseList = malloc(sizeof(LNode));
  reverseList->next = null;
  while(current != null) {
    headInsert(reverseList, current->data);
    current = current->next;
  }
  while(reverseList != null) {
    print(reverseList->data);
    reverseList = reverseList->next;
  }
}
1
2
3
4
5
6
7
8
9
//法二，利用递归实现。
void printReverse(LinkList L) {
  if (L->next != null) {
    printReverse(L->next); //递归到链表尾部，出栈
  }
  if (L != null) {
    print(L->data); //输出结果
  }
}
试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法 (假设最小值结点是唯一的)。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteMin(LinkList &L) {
  LNode *minPrior = L->next; //minPrior指向最小值节点的前一个节点
  LNode *p = L->next; //从第二个节点开始遍历
  while(p->next != null) {
    if (p->next->data < min->data) {
      minPrior = L;
    }
    p = p->next;
  }
  LNode *min = minPrior->next;
  minPrior->next = min->next->next;
  free(min);
}
试编写算法将带头结点的单链表就地逆置，所谓 “就地” 是指辅助空间复杂度为 O(1)。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//从链表头部开始遍历，利用头插法在原链表的基础上生成新链表，再遍历输出新链表的值即可。参考题3
LinkList headInsert(LinkList &head, Elemtype value) {//该方法默认链表带有头节点
  temp = (LNode*)malloc(sizeof(LNode));
  temp->data = value;
  temp->next = head->next;
  head->next = temp;
}

void Reverse(LinkList &L) {
  LNode *current = L->next;
  L->next = null;
  while(current != null) {
    headInsert(L, current->data);
    current = current->next;
  }
}
有一个带头结点的单链表 L，设计一个算法使其元素递增有序。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//使用插入排序的思想
void sortList(LinkList &L) {
  LNode *current = L->next;
  while(current->next != null) {
   if (current->next->data < current->data) { //如果后一个节点大小小于前一个节点
     LNode *locate = L; //从链表头部开始遍历寻找插入位置。
     while(locate->next !=null) {
       if (locate->next->data > current->next->data) { //找到第一个大于操作节点的位置
         LNode *next = current->next->next;
         current->next->next = locate->next;
         locate->next = current->next;
         current->next = next;
         break;
       }
       locate = locate->next;
     }
   } else {
     current = current->next;
   }
  }
}
设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值 (作为函数参数给出) 之间的元素的元素 (若存在)。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void rangeDelete(LinkList &L, int min, int max) {
  LNode *p = L->next, *pre = L;//pre用来记录每一轮p的前驱，便于删除操作。
  while(p != null) {
    if (p->data > min && p->data < max) { //找到删除点
      pre->next = p->next;			
      free(p);
      p = pre->next;
    } else { //搜索下一个节点
      pre = p;
      p = p->next;
    }
  }
}
给定两个单链表，编写算法找出两个链表的公共结点。

算法的代码描述如下：

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
//默认为带头节点的单链表，两链表的长度分别为m，n
//暴力解法为O(m*n)
int getLength(LinkList L) {
  int length = 0；
  while(L != null) {
    L = L->next;
    length++;
  }
  return length;
}

Linklist findCommon(LinkList L1, LinkList L2) {
  int len1 = getLength(L1), len2 = getLength(L2);
  if (len1 > len2) {
    int distance = len1 - len2;
    while (distance != 0) {
      L1 = L1->next;
      distance--;
    }
    while (len2 != 0) { //在减去多的距离之后，L1和L2到公共节点的距离相同。
      if (L1 == L2) {
        return L1;
      } else {
        L1 = L1 -> next;
        L2 = L2 -> next;
			}
    }
    return null;
  } else {
      int distance = len2 - len1;
      while (distance != 0) {
        L2 = L2->next;
        distance--;
      }
      while (len1 != 0) {
        if (L1 == L2) {
          return L1;
        } else {
          L1 = L1 -> next;
          L2 = L2 -> next;
        }
      }
      return null;
    }
}
给定一个带表头结点的单链表，设 head 为头指针，结点结构为 (data,next)，data 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间 (要求：不允许使用数组作为辅助空间)。

因为不能使用辅助空间，由第 6 题可知，空间复杂度为 O(1) 时，排序算法时间复杂度为 O(n2)。

而暴力解法的时间复杂度也是 O(n2)，所以直接两重循环，每次寻找最小元素输出。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void deleteMin(LinkList &L) {
  while(L->next != null) {
    LNode *pre = L, *p = L->next;
    while (p->next != null) {
      if (p->next->data < pre->next->data) {
        pre = p;      //记录此轮循环最小值节点的前驱
        p = p->next;
      }
    }
    print(pre->next->data);
    LNode *del = pre->next;
    pre->next = pre->next->next;
    free(del);
  }
  free(L);
}
将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

算法具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkList split(LinkList &A) {
  int i = 1;
  LNode *p = A->head;
  LNode *pre = A; //pre指向p的前驱节点
  LinkList B = (LinkList)malloc(sizeof(LNode));
  B->next = null;
  while(p != null) {
    if(i % 2 == 0) {
      LNode *temp = p->next;
      tailInsert(B, p->data); //尾插法
      pre->next = temp;
      p = pre;
      p = p->next;
    } else {
      pre = p;
      p = p->next;
    }
    i++;
  }
  return B;
}
设 C={a1,b1,a2,b2,..,am,bn} 为线性表，采用带头结点的 hc 单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A={a1,a2,...,an},B={bn,...,b2,b1}。

和上一题类似，生成链表 B 的时候采取头插法，则可得到倒置的链表 B。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkList split(LinkList &A) {
  int i = 1;
  LNode *p = A->head;
  LNode *pre = A; //pre指向p的前驱节点
  LinkList B = (LinkList)malloc(sizeof(LNode));
  B->next = null;
  while(p != null) {
    if(i % 2 == 0) {
      LNode *temp = p->next;
      headInsert(B, p->data); //头插法
      pre->next = temp;
      p = pre;
      p = p->next;
    } else {
      pre = p;
      p = p->next;
    }
    i++;
  }
  return B;
}
在一个递增有序的线性表中，有数值相同的元素存在。 若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素，例如 (7,10,10,21,30,42,42,42,51,70) 将变为 (7,10,21,30,42,51,70)。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteSame(LinkList &L) {
  LNode *p = L->next;
  LNode *next;  //next指向p的next节点。
  while(p->next != null) {
    next = p->next;
    if (next->data == q->data) {
      p->next = next->next;
      free(next);
    } else {
      p = p->next;
    }
  }
}
假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

算法的代码描述如下：

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
void mergeList(LinkList &L1, Linklist &L2) {
  LNode *p1 = L1->next, *p2 = L2->next;
  LNode *temp;     //用来暂存p1或者p2的后继节点
  L1->next = null; //最后结果返回L1
  while(p1 != null && p2 != null) {
    if (p1->data < p2->data) {
      temp = p->next;
      p1->next = L1->next; //头插法
      L1->next = p1;
      p1 = temp;
    } else {
      temp = p->next;
      p2->next = L2->next;
      L1->next = p2;
      p2 = temp;
    }
    while(p2 != null) { //如果L2仍有元素剩余，将其头插插入L1。
			temp = p2->next;
      p2->next = L1->next;
      L1->next = p2;
      p2 = temp;
    }
    free(L2);
  }
}
设 A 和 B 是两个单链表 (带头结点)，其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C, 要求不破坏 A，B 的结点。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getCommon(LinkList &A, LinkList &B) {
  LNode *p = A->next, *q = B->next;
  LinkList C = malloc(sizeof(LNode));
  LNode *tail; //tail是新链表C的尾指针
  C->next = null;
  while(p != null && q != null) {
    if (p->data == q->data) {
      LNode temp = (LNode*)malloc(sizeof(LNode));
      temp->data = p->data;
      tail->next = temp; //尾插法
      tail = temp;
      p = p->next;
      q = q->next;
    } else if (p->data < q->data) {
      p = p->next;
    } else {
      q = q->next;
    }
  }
  tail->next =null;
}
已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。编制函数，求 A 与 B 的交集，并存放于 A 链表中。

算法的代码描述如下：

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
void union(LinkList &A, LinkList &B) {
  LNode *p1 = A->next, *p2 = B->next; //p1，p2分别为A，B链表的工作指针
  LNode *pre = A; //pre指向p1的前驱，防止A断链
  while(p1 != null || p2 != null) {
    if (p1->data == p2->data) {
      p1 = p1->next;
      LNode *temp = p2;
      p2 = p2->next;
      pre = pre->next;
      free(temp);  //释放B链表中的重复节点。
    } else if(p1->data < p2->data) {
      LNode *temp = p1;
      pre->next = p->next;
      p1 = p1->next;
      free(temp);
    } else {
      LNode *temp = p2;
      p2 = p2->next;
      free(temp);
    }
    while(p1 != null) { //释放A中的剩余节点
      LNode *temp = p1;
      p1 = p1->next;
      free(temp);
    }
    while(p2 != null) { //释放B中的剩余节点
    	LNode *temp = p2;
      p2 = p2->next;
      free(temp);
    }
    pre->next = null;
    free(B);
}
两个整数序列 A=a1,a2,a3,...,am 和 B=b1,b2,b3,..,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的连续子序列。

默认为带头节点的单链表，类似于模式匹配算法。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isSubseq(LinkList A, LinKList B) {
  LNode *p1 = A->next, *p2 = B->next;
  LNode *pre = p;
  while(p1 != null && p2!=null) {
    if(p1->data == p2->data) {
      p1 = p1->next;    //A，B指针一同后移
      p2 = p2->next;
    } else {
      pre = pre->next; //A在原基础上后移一位
      p1 = pre;
      p2 = B->next;
    }
  }
    if (p2 == null) { //B链表走到表尾
      return true;
    } else {
      return false;
    }
}
设计一个算法用于判断带头结点的循环双链表是否对称。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
bool symmetry(DLinkList L) {
  DNode *p = L->next, *q = L->prior;
  while(p != q && p->prior != q) { //奇数，偶数循环结束条件不同
    if (p->data == q->data) {
      p = p->next;
      q = q->prior;
    } else {
      return false;
    }
  }
  return true;
}
有两个循环单链表，链表头指针分别为 h1 和 h2，编写一个函数将链表 h2 链接到链表 h1 之后，要求链接后的链表仍保持循环链表形式。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
LinkList link(LinkList &h1, LinkList &h2) {
  LNode *p = h1, *q = h2; //p,q分别为两个链表的尾指针
  while(p->next != p) {
    p = p->next;
  }
  while(q->next != q) {
    q = q->next;
  }
  p->next = h2;
  q->next = h1;
  return h1;
}
设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void deleteAll(LinkList &L) {
  LNode *p, *pre, *minp, *minpre; 
  while(L->next != L){
    p = L->next; 
    pre = L;
    minp = p;     //minp指向最小值结点
    minpre = pre; //minpre指向最小值节点的前驱
    while(p != L) { //循环一趟,查找最小值结点
    	if(p->data < minp->data){
    	minp=p; //找到值更小的结点
    	minpre=pre;
      }
      pre = p;    //查找下一个结点
      p = p->next;
    }
    printf("%d", minp->data);
    minpre->next = minp->next;
    free(minp);
    } 
    free(L);
}
设头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred (前驱指针)，data (数据) 和 next (后继指针) 域外，还有一个访问频度域 freq。在链表被启用前，其值均初始化为零。每当在链表中进行一次 Locate (L,x) 运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增 (递减) 的顺序排列，同时最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头。 试编写符合上述要求的 Locate (L,x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

算法的代码描述如下：

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
DLinkList Locate(DLinkList &L, ElemType x){
//本算法先查找数据x,查找成功时结点的访问频度域增1
//最后将该结点按频度递减插入链表中适当位置(同频度最近访问的在前面)
  DNode *p = L->next, *q; //p为工作指针,q为p的前驱,用于查找插入位置
  while(p != null && p->data != x) {
    p = p->next;   //查找值为x的结点
  }
  if( p == null) {
    printf("不存在值为x的结点");
    return 0;
  } else {
    p->freq++;  //令元素值为x的结点的freq域加1
    if(p->next != NULL) {
      p->next->pred = p->pred;
    }
    p->pred->next = p->next;//将p结点从链表上摘下
    q = p->pred;
    while(q != L && q->freq <= p->freq) {
      q = q->pred;//以下查找p结点的插入位置
    }
    p->next = q->next; //将p结点插入,一定是排在同频率的第一个
    q->next->pred = p;
    p->pred = q;
    q->next = p;
  }
  return p;
}
已知一个带有表头结点的单链表，结点结构为 (data,link)，假设该链表只给出了头指针 list。 在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点 (k 为正整数)。 若查找成功。算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求:
  1. 描述算法的基本设计思想。
  2. 描述算法的详细实现步骤。
  3. 根据设计思想和实现步骤，采用程序设计语言描述算法 (使用 C、C++ 或 Java 语言实现)，关键之处请给出简要注释。

    解答：

    暴力解法可以通过遍历两次解决，时间复杂度为 O(n2)。问题的关键如何通过链表的一次遍历，找到倒数第 k 个结点的位 置。算法的基本设计思想是：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点 (链表的第一个结点)，p 指针沿 链表移动；当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为 倒数第 k 个结点。 以上过程对链表仅进行一遍扫描.

​ 步骤：

  1. count 初始化为 0，计数，p，q 指向链表的第一个节点；

  2. p 为空，转 5；

  3. 如果 count == k​，p，q 同时后移，直到 p 到链表尾部；否则， count++​，p 单独后移（阶段一），转 2。

  4. 如果 count < k，说明 k 值超过了链表长度，返回 false。反之 count == k，查找成功，输出 q->data，算法结束。

    算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool searchK(Linklist L, int k) {
  LNode *p = L->next, *q = L->next;
  int count = 0;
  while(p != null) {
    if (count < k) {
      p = p->next;
      count++;
    } else {
      p = p->next;
      q = q->next;
    }
  }
  if (count < k) {
    return false;
  } else {
    print("%d", q->data);
    return true;
  }
}

​ 解答：

  1. 如题 8，目的是找到两链表的第一个公共节点。计算两链表的长度差值 dist，设置指针分别指向两链表，让指向长链表的指针先前进 dist 距离。之后，两指针同步后移，比较两指针指向的地址。如果地址相同则找到了目标节点。

  2. 算法的代码描述如下：

    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
       //默认为带头节点的单链表，两链表的长度分别为m，n
       int getLength(LNode *str) {
         int length = 0；
           while(str != null) {
             str = str->next;
             length++;
           }
         return length;
       }
       
       LNode findCommon(LNode *str1, LNode *str2) {
         int len1 = getLength(str1), len2 = getLength(str2);
         if (len1 > len2) {
           int distance = len1 - len2;
           while (distance != 0) {
             str1 = st1->next;
             distance--;
           }
           while (len2 != 0) { //在减去多的距离之后，L1和L2到公共节点的距离相同。
             if (str1 == str2) {
               return str1;
             } else {
               str1 = str1 -> next;
               str2 = str2 -> next;
             }
           }
           return null;
         } else {
           int distance = len2 - len1;
           while (distance != 0) {
             str2 = str2->next;
             distance--;
           }
           while (len1 != 0) {
             if (str1 == str2) {
               return L1;
             } else {
               str1 = str1 -> next;
               str2 = str2 -> next;
             }
           }
           return null;
         }
    }

  3. 时间复杂度为 O(max(len1,len2))。

​ 解答：

  1. 因为 |data|≤n，考虑构建长度为 n+1 的辅助数组，初始化为零。用来判断该值是否出现过。在此情况下，只需遍历一次，即可完成全部操作。

  2. 单链表结点的数据类型定义如下：

    1
    2
    3
    4
    5
    typedef struct node {
    	int data;
    	struct node *next;
    }NODE;
    typedef NODE *Pnode;

  3. 具体算法如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
      void deleteNode(Pnode target, Pnode pre) {
        pre->next = target->next;
        free(target);
      }
      
      void deleteAbs(Pnode head, int n) {
        int array[n + 1];
        for(int i = 0; i < n + 1, i++) {
          array[i] = 0;
        }
        while(head->next != null) {
          int absValue = (head->next->data > 0) ? (head->next->data) : -(head->next->data);
          if(array[absValue] == 0) {
            array[absValue] = 1;
            head = head->next;
          } else {
            deleteNode(head->next, head);
          }
        }
    }

  4. 时间复杂度 O(m)，空间复杂度 O(n)。

判断一个链表是否有环，如果有，找出环的入口点并返回，否则返回 NULL。

设置快慢两个指针分别为 fast 和 slow，初始时都指向链表头 head。slow 每次走一步，即 slow=slow->next；fast 每次走两步，即 fast=fast->next->next。由于 fast 比 slow 走得快，如果有环，fast 一定会先进入环，而 slow 后进入环。 当两个指针都进入环后，经过若干次操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环。 如下图所示，当 slow 刚进入环时，fast 早已进入环。因为 fast 每次比 slow 多走一步且 fast 与 slow 的距离小于环的长度，所以 fast 与 slow 相遇时，slow 所走的距离不超过环的长度。

如下图所示，设头结点到环的入口点的距离为 a，环的入口点沿着环的方向到相遇点的距离为 x，环长为 r，相遇时 fast 绕过了 n 圈。则有 2(a+x)=a+n∗r+x，即 a=n∗r−x。显然从头结点到环的入口点的距离等于 n 倍的环长减去环的入口点到相遇点的距离。 因此可设置两个指针，一个指向 head，一个指向相遇点，两个指针同步移动 (均为一次走一步)，相遇点即为环的入口点。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LNode* findLoop(LinkList L) {
  Lnode *fast = L->next->next, *slow = L->next;
  while(fast != slow && fast != null) {
    slow = slow->next;
    fast = fast->next->next;
  }
  if(fast == null) { //没有环
    return null；
  } else {
    LNode *p1 = L;
    while(p1 != slow) { //寻找相遇点
      p1 = p1->next;
      slow = slow->next;
    }
    return p1; //p1即为入口点
  }  
}

​ 解答：

  1. 新链表由原链表的前半部分，以及后半部分倒序交错组成。思路：找到中间节点，通过头插法将后半部分倒序。在对两部分链表交替取值，以原链表头节点为基础，通过尾插法生成结果链表。

    中间节点可以通过设置指针 p 和 q，指针 p 每走一步，q 走两步，这样当 q 到链尾时，指针 p 恰好指向中间节点。

  2. 算法的代码描述如下：

    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
      void resort(LNode *head) {
        LNode *p = head, *q =head;
        LNode *temp, *insert;
        while(q->next != null) {
          p = p->next;
          q = q->next;
          if (q->next != null) {
            q = q->next;
          }
        } //此时p指向中间节点，q指向链尾节点。
        q = p->next;
        p->next = null;
        while(q != null) { //头插法，将后半部分逆置
          temp = q->next;
          q->next = p->next;
          p->next = q;
          q = temp;
        }
        insert = head->next; //insert指向前半段的一个数据节点，插入位置
        q = p->next; 				 //q指向后半段的第一个数据节点
        p->next = null;			 //设置链尾为null
        while(q!) {
          temp = q->next;
          q->next = insert->next;
          insert->next = q;
          insert = q->next;  //跳过一个点，交错插入
          q = temp;
        }
    }

  3. 时间复杂度：寻找中间节点 O(n)，逆置时间复杂度 O(n)，合并链表的时间复杂度 O(n)。所以整体的时间复杂度为 O(n)。

Powered By Valine
v1.5.2