链表刷题集_遍历单链条时间复杂度

单链表刷题

移除链表元素

解法一：遍历链表一遍，按照单链表删除操作(删除中间需要记录前一个位置)进行即可，时间复杂度o（n）

注意点:头元素是要删除的元素，大量重复元素

反转单链表

解法一:新建一个没用的节点(带哨兵位的NULL)，从前往后搜索,在新节点的后面依次往前插入节点。

时间复杂度O(N)

解法二：三指针prev，cur，next指针。

 注意点：零个节点(空链表，直接返回)，一个节点()，两个节点

next为空的状态，不能再指向下一个节点了,需要单独处理

时间复杂度O(N) 

 链表的中间节点

解法一:遍历一遍，记录counts，除以二，再遍历到counts/2的位置，返回即可.

奇数：5/2=2,+1

偶数：6/2=3,+1

时间复杂度o（n+n/2）

解法二:快慢指针，快指针一次走两步，慢指针一次走一步，时间复杂度O（n）

 如何理解？假定fast最后走完全程为1，slow为fast的几分之几或者几倍，就走多少距离，即可实现要求停止的位置.

链表中倒数第k个结点

解法一：遍历一遍记录counts，然后减去counts-k，然后顺序遍历链表，就能找到第k个节点.

时间复杂度O(N+N-K)

解法二 ：先逆置单链表，然后顺序遍历链表，时间复杂度O(N+N-K)

解法三：快慢指针，fast先走k步，然后两个指针一起走，这样，当fast走到尾的时候，他们的差距永远在k，fast的位置正好就是counts，slow的位置正好也是counts-k;时间复杂度O(N)

注意点：k的值并未告诉你，是否在合适的范围呢，k=0？k>链表长度？

1：取模是否可以？不知道链表长度，好像不行

2：fast在先走某个步数时就已经为空了，则说明，k的值大于了链表长度，此时直接返回即可

合并两个有序链表

解法一：归并排序，依次比较大小。尾插，不支持从后面开始

注意点：1：如果不记录新链表的尾指针，那么时间复杂度时O(N方)，因为每次都要找尾指针的位置，构成等差数列。如果记录尾指针，那么时间复杂度为O(N)

2：肯定会有一个先结束。结束的那个，直接链接到后面(升序)。

如果使用不带头的单链表，则需要判断是否为第一次插入。

如果使用带头的单链表，则不需要判断是否为第一次插入

链表分割

描述：

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

解法一：遍历一遍链表，分为两个，小于数字x的存入小链表，大于等于数字x的存入大链表，

接着小链表的后面连接上大链表即可，时间复杂度O(N)

注意点：1：避免判断第一次是否为空，使用带头的单链表，小链表的哨兵位的next为头。小链表的尾的next链接大链表的哨兵位的next。

2：内存超限，一般是链表中有死循环。这个题最后链接可能会导致链表带环

 3：因为使用两个链表，因此lesshead和lesstail刚开始创建哨兵位的时候必须要指向同一块空间，这样才能带头哨兵位才能连接上插入进来的数据

        lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lesshead=lesstail;
        greaterhead=greatertail;

 链表的回文结构

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

解法一：先找到中间节点，逆置中间节点的后半部分，从头和从逆置后的中间节点开始遍历。时间复杂度O(N+N+N)

难题

复制带随机指针的链表

 解法一(普通人)：模拟数组。用给节点编号，从0开始。比如：遍历原链表，13的random指向7，用一个变量记录下来，这是第一个节点，记为0。用这个counts=0，再次遍历链表，让13的random链接上去。时间复杂度o（n*n）---好慢。。

有没有更好的方法？

题解：(大神思维):

这道题可以顺藤摸瓜。

假设有A把B藏起来了，我们可以全世界找B，这是第一种方法。

我们还可以设置一个陷阱，让A以为我们找到了B，然后顺着A，找B。这是第二种方法。

1.拷贝节点到源节点后面，时间复杂度O（n）

 2.拷贝节点的random指针指向源节点的random，时间复杂度O（n）

3.对链表解链 ，时间复杂度O（n）

最终时间复杂度O（N）！！！

 

 

 

相交链表刷题

 相交链表

描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解法一：判断相交思路：遍历A与B，看尾节点是否一样，如果尾节点一样，则一定相交（不一定能找到第一个相交的节点，只能判断是否相交），o（m+n）。记录长度，做差值，长的那个先走差值步数。一起走，看下一个地址(除了NULL)是否相等。相等则相交.时间复杂度o（M+N+M+N）

解法二：遍历A链表，看A的地址是否在B中。时间复杂度O(N*M)---几乎n方了

环形链表刷题

环形链表

求入口点

重要的不是代码，代码很简单，重要的是证明的思路。