lintcode 链表总结

翻转链表问题

35、翻转链表

样例：给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

若所翻转链表无头结点

a.     头插法

思路：每次都像头节点的后面插入元素，需要定义头节点 

b.    就地逆置

思路：三指针法，先定义当前结点，前向结点和后继结点，然后一步一步移动这几个结点，不需定义头结点

若所翻转链表有头结点

a.     头插法

思路：每次都像头节点的后面插入元素，不需定义头节点 

b.    就地逆置

思路：三指针法，先定义当前结点，前向结点和后继结点，然后一步一步移动这几个结点，头结点保持不动

36 翻转链表2

翻转链表中第m个节点到第n个节点的部分

 注意事项

m，n满足1 ≤ m ≤ n ≤ 链表长度

给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null

主要思想：找到需要翻转的m,n结点及其前一、后一结点，以便后期插入使用。
需要考虑边界情况：
1、当m=1时，无前向结点
2、m,n均在中间时与n在结尾时可以归类为同一种情况
3、在while()语句中进行m的递增递减时，注意m的变化，因为后面也要用m,此时m已经变化，最好找另外变量先储存m的值。

其他：

(1)   指定某一段子链翻转（92. Reverse LinkedList II, Medium）

思路：指定第m到第n个节点翻转，先用一个节点指向第m个节点的前驱，后面n-m+1个节点都向这个位置插入。

(2)   每个等长的子链翻转（24. Swap nodes inpairs, Medium）（25.Reverse Nodes in k-Group, Hard）

思路：24.对每两个元素进行翻转。需要两个指针指向这个pair，通过将前面的节点放在后面的节点后面来翻转两个节点比把后面的节点放在前面的节点前面操作简单，因为往前插入，需要有前一个的指针。

思路：25.对每k个元素进行翻转，最后剩余不够k个元素则不进行翻转。先要计算链表中元素个数，这个个数也作为剩余的元素数量，根据这个数量判断是否继续下一组k个元素翻转，每次翻转一组元素后要更新这个值。每次k个元素采用头插法，只需要固定二个位置，一个是头节点（需要插入元素的前驱结点），一个是需要移动的节点的前驱结点。时间复杂度O(2n)，空间复杂度O(1)

(3)   判断链表是否是回文（234. PalindromeLinked List, Easy）

思路：先找到中间的节点，翻转后半个链表，之后和前半部分链表比较，时间复杂度O(n)，空间复杂度O(1)

（4）旋转链表，向左旋转k个元素=向右旋转n-k个元素（61. Rotate List, Medium）

思路：后半部分（k, n-1）和前半部分（0，k-1）颠倒位置。首先k可能大于n，所以k%=n，之后将链表首尾相连，形成环，从链表开头移动n-k个位置断开环，k个位置的下一个位置作为head，即为所求。

 链表划分

96 链表划分

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。

你应该保留两部分内链表节点原有的相对顺序。

样例

给定链表 1->4->3->2->5->2->null，并且 x=3 ，返回 1->2->2->4->3->5->null

(1)   小于x的节点在前面，大于x的节点在后面（96. Partition List ）

(2)   奇数放在前面，偶数放在后面（328. Odd EvenLinked List, Medium）

解题思路：创建两个新链表，分别设为1,2；遍历给定链表，比较每个结点与给定值X值的大小，若比X小，则放入新链表1中，否则放入新链表2中。遍历完毕后，将新链表1 的最后一个结点指向新链表2的第一个结点，来达到将两个链表串起来从来实现划分链表的目的。（2）思路相同

链表去重

112. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素每个元素只留下一个。

给出 1->1->2->null，返回 1->2->null

给出 1->1->2->3->3->null，返回 1->2->3->null

思想：通过比较前一个结点值与后一个结点值是否相等，来决定当前结点指向后一个结点or后一个结点的后一个结点

113. 删除排序链表中的重复数字 II

给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。

给出 1->2->3->3->4->4->5->null，返回 1->2->5->null

给出 1->1->1->2->3->null，返回 2->3->null

a：立flag法，通过先将每个结点值存到val里，然后后面值与val比较，若相等则head->next=head->next->next，再比较，直到不相等，则更新val的值

b:递归法,3->3->2->1->null

p首先指向第二个3，val值为第一个3，判断：如果p与val相等则p移向下一个，继续调用deleteDuplicates函数

若链表为3->1->1->3->null，即p与val不相等，则head->next指向函数调用之后的值。即能救出来一个是一个。

找主元素

48. 主元素 II

给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。（数组中只有唯一的主元素）

样例

给出数组 [3,1,2,3,2,3,3,4,4,4] ，和 k = 3，返回 3

a: hash表,用hash表来存储每个元素出现的次数，这样就可以得到一个时间复杂度和空间复杂度都是O(n)的解决方案。这里我们不自己构造hash函数，使用C++自带的unorderwd_map或者map，时间上也不是很快。

b:随机化方法，每次随机产生一个位置，对这个位置的数进行计数，看是不是主元素，时间O(n)。

链表排序问题

165. 合并两个排序链表

将两个排序链表合并为一个新的排序链表

样例

给出 1->3->8->11->15->null，2->null， 返回1->2->3->8->11->15->null。

思想：因为两个链表均是排好序的，因此只需要新建一个链表，将两个链表进行大小对比后，存放在新链表中即可。

注意：两个链表不同长度的处理方法。

104. 合并k个排序链表

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度

样例

给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null

a、逐个合并，以合并两个排序链表为基础

b、采用归并的方法来解决这个问题，其有K个链表，不断将其划分（partition），再将其归并（merge）。

    划分的部分并不难，将其不断分成两部分，但是需要注意的是可能出现start和end相等的情况，

     这时候就直接return lists[start]就可以了。 

98 链表排序

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

样例

给出 1->3->2->null，给它排序变成 1->2->3->null.

a、归并排序法，算法思想是首先用快慢指针的方法找到链表中间节点，然后递归地对两个子链表进行划分排序，

排序函数与两个排序链表的排序思想一样。归并排序算是链表排序中的最好选择，保证了最好和最坏时间复杂度都是O(n log n)。

b、快速排序法，快速排序的主要思想是： 
　　 1）选定一个基准元素 
　　 2）经过一趟排序，将所有元素分成两部分 
　　 3）分别对两部分重复上述操作，直到所有元素都已排序成功 

使用递增排列的链表创建平衡二叉树BST

106. 排序列表转换为二分查找树

给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树

样例

               2
1->2->3  =>   / \
             1   3

思路：递增排序相当于是平衡二叉树的中序遍历，所以构建树时要按照中序。

利用递归进行中序遍历链表生成平衡二叉树。每次要取链表中间位置的节点作为root。

利用快慢指针问题

99. 重排链表

给定一个单链表L: L0→L1→…→Ln-1→Ln,

重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的情况下进行原地操作

样例

给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null。

思路：1、将链表等分（利用快慢指针）

           2、将第二个链表翻转

          3、 交叉合并链表

102 带环链表

给定一个链表，判断它是否有环。

给出 -21->10->4->5, tail connects to node index 1，返回 true

思想：利用快慢指针，如果有环，则快慢指针最终会相等（fast==slow），如果没环，fast指针最终等于NULL

103 带环链表 II

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。

样例

给出 -21->10->4->5, tail connects to node index 1，返回10

思路：看图

其他

（1）移除指定节点，思路：利用两个指针，一个指针先向前走k步，之后两个指针每次走一步，

直到先走的指针走到链表结尾节点，第二个指针指向的位置就是要删除的节点的前驱，再删除其后的节点。

(2)    寻找单链表的中心（143）

一个指针p1每次走一步，另一个指针p2每次走两步，当链表为奇数个时，p2指向尾节点（p2->next = NULL）时，

p1就是链表的中心节点。当链表为偶数个时，p2指向NULL时，p1和p1->next这两个节点为链表的中心节点。

（3）查找两个链表的公共节点，思路：先计算两个链表的长度，长的链表将指针移动到和短的链表看齐的位置，

 之后齐头并进扫描，如果两个指针相同，那么就找到公共节点了。

(4)    判断链表的奇数个元素还是偶数个元素（143.Reorderlist, ）

一个指针p1每次走一步，另一个指针p2每次走两步，如果p2最后满足p2&&p2->next = NULL那么链表就是奇数个元素。

思路：143.需要综合运用对链表的多个操作方法。首先利用快慢指针，找到链表的中心并判断链表奇偶，如果是奇数个，则p1向后移动一个位置，这样就将链表分成了两部分。之后将后半部分进行逆序。最后将后半部分的元素分别插入到前半部分元素中间。

复制带随机指针的链表

105. 复制带随机指针的链表（具体做题）

思路：难点在于随机指针，想要顺序的深度拷贝链表是行不通的，因为后面节点的还没有创建可能前面的节点就要指向它，

还有要考虑如何指向对应的位置。