# 链表常见问题（上）

### 1.从尾到头打印单链表

```void SListPrintTailToHead(SListNode* pHead) { //1.定义两指针cur，tail分别指向链表头和尾，cur往后走cur->_next遇到tail,打印cur所指内容 //2. tail再往前走，最后到头结点结束 //
SListNode* tail = NULL; SListNode* cur = NULL; while (tail != pHead) { cur = pHead; while (cur->_next != tail) { cur = cur->_next; } printf("%d ", cur->_data); tail = cur; } }//递归实现 void SListPrintTailToHeadR(SListNode* pHead) { if(pHead == NULL) return; SListPrintTailToHeadR(pHead->_next); printf("%d ",pHead->_data); }```

### 2.删除一个无头单链表的非尾节点（不能遍历链表）

```void SListDelNonTailNode(SListNode* pos) { //覆盖替换法删除
assert(pos && pos->_next); SListNode* next = pos->_next; pos->_data = next->_data; pos->_next = next->_next; free(next); }```

### 3.在无头单链表的一个结点前插入一个结点（不能遍历链表）

`void SListInsertFrontNode(SListNode* pos, DataType x){`
` assert(pos); //直接在该结点后插入一个_data的值与该结点的_data相同的结点 //修改该节点的_data的值为x即可 SListNode* newNode = BuySListNode(pos->_data); newNode->_next = pos->_next; pos->_next = newNode; pos->_data = x; }  `

### 4.单链表实现约瑟夫环(JosephCircle)

(其实就和小时候玩丢手绢游戏差不多）如每数到4就去掉一个人：

```SListNode* SListJosephCircle(SListNode* pHead, int m) { SListNode* cur = pHead; SListNode* next; //链成环
while(cur->_next){ cur = cur->_next; } cur->_next = pHead; cur = pHead; while (cur->_next != cur) { size_t count = m;   //每数到m 去掉这个人
while (--count) { cur = cur->_next; } //替换删除法
next = cur->_next; cur->_data = next->_data; cur->_next = next->_next; free(next); next = NULL; } return cur; } 结果：```

### 5.逆置/反转单链表

```法一：SListNode* SListReverse1(SListNode* list) { assert(list); //注意需要三个指针来进行迭代着往后进行逆置

if(list == NULL || list->_next == NULL) return list; SListNode* n1 = list; SListNode* n2 = list->_next; SListNode* n3 = n2->_next; while(n2 != NULL){ n2->_next = n1; if(n1->_next == n2)  //解除环路
n1->_next = NULL; n1 = n2; n2 = n3; if(n3 != NULL) n3 = n3->_next; } return n1; }法二： SListNode* SListReverse2(SListNode* list){ SListNode* ptmp = NULL; SListNode* cur = list; //利用中间变量来逆置
while (cur != NULL) { SListNode* next = cur->_next; cur->_next = ptmp; ptmp = cur; cur = next; } return ptmp; } ```

### 6.单链表排序（冒泡排序&快速排序）

```//冒泡排序void SListBubbleSort(SListNode* list){ SListNode* end = NULL; //交换时交换每个结点_data的值即可
while(end != list){ SListNode* cur = list; SListNode* next = list->_next; int flag = 0;   //标记位

while(next != end){ if(cur->_data > next->_data){ flag = 1; DataType temp = cur->_data; cur->_data = next->_data; next->_data = temp; } cur = cur->_next; next = next->_next; } if(flag == 0) return ;  //链表基本有序 跳出循环
end = cur; } }```

### 7.合并两个有序链表,合并后依然有序

```// 升序 SListNode* SListMergeR(SListNode* list1, SListNode* list2) { //递归实现 assert(list1 || list2);  //list1 list2 不能同时为空

if(list1 == NULL) return list2; else if(list2 == NULL) return list1; SListNode* newList = NULL; if(list1->_data < list2->_data){ newList = list1; newList->_next = SListMergeR(list1->_next,list2); } else{ newList = list2; newList->_next = SListMergeR(list1,list2->_next); } return newList; } //非递归实现 SListNode* SListMerge(SListNode* list1, SListNode* list2){ assert(list1 || list2); if(list1 == NULL) return list2; else if(list2 == NULL) return list1; SListNode* newList = NULL; //确定好newList指向的第一个结点 if(list1->_data < list2->_data){ newList = list1; list1 = list1->_next; //细节 } else{ newList = list2; list2 = list2->_next; } SListNode* cur = newList; //确定后面的结点

while(list1 && list2){ if(list1->_data < list2->_data){ cur->_next = list1; list1 = list1->_next; } else{ cur->_next = list2; list2 = list2->_next; } cur = cur->_next; }if(list1 == NULL){ //接上残余的链表 cur->_next = list2; } else{ cur->_next = list1; } return newList; }```

### 8.查找单链表的中间节点，要求只能遍历一次链表

```SListNode* SListFindMidNode(SListNode* list) {
assert(list);
//定义快慢指针，快指针一次往后走两个结点，慢一次走一个结点，
//快指针走到末尾，慢指针指向中间节点
SListNode* fast = list;
SListNode* slow = list;

while(fast && fast->_next){
fast = fast->_next->_next;
slow = slow->_next;
}
return slow;
}```

### 9.查找单链表的倒数第k个节点，要求只能遍历一次链表

```//类似上面，同样定义快慢指针，让快指针提前指向第K个结点SListNode* SListFindTailKNode(SListNode* list, size_t k) {
assert(list);

SListNode* slow = list;
SListNode* fast = list;
while(k--){
fast = fast->_next;
if(fast == NULL){
printf("Find Tail K Node failed!\n");
return NULL;
}
}

while(fast){
fast = fast->_next;
slow = slow->_next;
}
return slow;
}
```

### 10.删除链表的倒数第K个结点

```void SListDelTailKNode(SListNode* list, size_t k){
assert(list);

SListNode* slow = list;
//fast提前指向第K+1个节点
SListNode* fast = list->_next;
while(k--){
fast = fast->_next;
if(fast == NULL){
printf("Deltel Tail K Node failed!\n");
return ;
}
}
//fast slow 同时往后走
while(fast){
fast = fast->_next;
slow = slow->_next;
}
SListNode* next = slow->_next;
slow->_next = next->_next;
free(next);
next = NULL;
}```

原文作者：tp_16b
原文地址: https://www.cnblogs.com/tp-16b/p/8183267.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。