三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

单链表:找中间节点、找倒数第k节点、是否有环、逆序、排序(选择、冒泡、插入)

单链表:找中间节点、找倒数第k节点、是否有环、逆序、排序(选择、冒泡、插入)

一. 找链表的中间节点(两种方法)

1、通过链表长度(简单,不推荐)

2、快慢指针(推荐)

分奇偶数个节点 当奇数:pf走到NULL 或 偶数:pf走到尾节点 时,ps刚好在中间。


二. 找倒数第 k 个节点(把尾节点当倒数第一个)

1、同样可以用长度 len-k(不推荐)

2、双指针(从头节点开始;如果从首节点开始的话,最后一个数找不到)


4. 判断链表是否有环(想象跑步套圈)

如何验证---需要建一个环:利用 "找倒数第 k 个节点" :这里找两个再把他们连起来形成环

node_t *p1 = find_end_k(phead,1);

node_t *p2 = find_end_k(phead,4);

p1->pnext = p2;


5. 链表逆序


6. 排序(针对单链表)

6.1 选择排序(找位置、找数、交换)

6.2 冒泡排序(趟数、比较次数、交换)

6.3 插入排序(原地插入)
← 返回列表