链表相关算法

链表节点的一般定义:

typedef struct ListNode
{
    DataType data;
    struct ListNode* next;
    /* struct ListNode* prev; */ /* 双向链表 */
} ListNodePtr;

从链表还衍生出很多著名的数据结构,比如循环队列跳表,都值得学习。

常见问题

问题1

给出一个单向链表的头指针,判断是否有环。

思路:俩指针追逐,步进分别为1和2,若有环,这俩指针将相遇。

问题2

给出两个单向链表的头指针,判断这两个链表是否相交。

思路:判断尾指针是否相同,判断有环的情况。

找到相交的那个节点。

思路:需要先遍历两个单向链表,并记录下各自长度;然后,求俩长度之差值,较长的链表先步进该差值,然后再一起步进。

问题3

输入一个单向链表,输出该链表中倒数第k个结点。

思路:设置两个指针p1,p2,首先p1和p2都指向head,然后p2向前走k步,这样p1和p2之间就间隔k个节点,最后p1和p2同时向前移动,直至p2走到链表末尾。

问题4

逆序输出链表。

思路:使用递归,递归结束条件为尾指针,然后逐个弹栈输出。

问题5

输出单链表的中间节点

思路:同样,俩指针追逐,步进分别为1和2,快指针指向链表尾时,慢指针指向中间节点。注意处理奇偶边界即可。

2006-04-15 23:05
status: part
comments powered by Disqus