找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 12621|回复: 38
收起左侧

[刷题总结] 【学习小结】如何对付面试中的链表题目

  [复制链接]

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 2-17-2016 01:05 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-21-2016 03:13 PM 编辑

这个是小弱一个对于链表题目的总结。(还没写完,挖个坑先)
=======================广告开始==============================
【第一弹】【LeetCode小分队】 刷题活动正在火热进行。请大家积极参与讨论,多多交流。
我们的口号是:现在多犯错,面试必须过!

汇总贴 传送门
=======================广告结束,转载开始=======================
先上好货, 来自大牛们的总结。http://cslibrary.stanford.edu/105/LinkedListProblems.pdf (这个我没怎么看)
java面试大总结:http://blog.csdn.net/fightforyourdream/article/details/16353519
Yu牛人笔记: https://www.zybuluo.com/smilence/note/128
=======================转载结束==============================
主要会对这三个资源中出现的链表题目总结
LeetCode 代号LC
CC 150 代号CC
EPI 代号EPI (optional)
=============================================================
LeetCode中的链表题目根据考察点或解题方法可以分为以下几个类别:一共24道题目。希望大家看完这篇总结都能轻松解答这24道题目。
1. =====  Remove=====
[LC]Remove Duplicates from Sorted List
题目:删除有序单链表中重复元素,令每个元素只出现一次。
思路:  维护pre和cur。pre指向当前的不重复的最后一个元素(有可能马上就又重复了),cur进行依次扫描,当遇到了非重复的元素时就更新pre.
其他:

[LC]Remove Duplicates from Sorted List II
题目:删除有序单链表中,所有出现了重复的元素 ,令其他元素只出现一次。
(输入 1->2->3->3->4->4->5, 返回1->2->5)
思路:维护pre和cur,思路和I很相似,只是pre指向上一个最后的不重复元素(已经被确认过不重复的元素)。
其他:

------------
小结:
LeetCode还有两个轻松变型:
[LC]Remove Duplicates from Sorted Array I
[LC]Remove Duplicates from Sorted Array II

2. =====双指针=====
全名是:双指针定位大法
第一次听说,双指针是在peking2二爷的LeetCode难度系数表里。后来在cc150里链表那一章看到了walker/runner方法。
我们最关心的2个指针如何变化。(我习惯叫slow/fast)

[LC]Linked List Cycle
题目:判断单链表里是不是有环。
思路:可以用额外空间HashTable做,也可以用walker/runner(双指针)做

点评:这题不难,但有时候拎不清。
说得通俗一点,如果链表有环,那么一个指针遍历该链表,就进入了无限循环,走不到头。
那么我们用两个指针呢?这两个指针一快一慢一定会在环中相遇。(请画图, 这是这道题的核心原理)
所以初始条件slow = fast = head. 终止条件是fast = null 或fast.next = null
fast = null的意思是快节点已经离开链表了。fast.next = null 为快节点到达链表尾节点。
如果中间slow和fast相等了,说明有环。其他情况均无环。

[LC]Linked List Cycle II
题目:判断单链表里是不是有环,并返回环的起始点。
思路: 用walker/runner(双指针)做,还涉及到一个数学公式
其他:Cc150里也有。

[LC]Remove Nth Node From End of List
题目: 删除单链表里倒数第N个节点并返回头节点。
思路:关键点就是如何找到倒数第N个节点,用walker/runner(双指针)做
其他: Cc 150里一个很类似的题目,找到链表的倒数第k个节点。

[LC] Rotate List
题目: 将链表右旋k个节点。
思路:用双指针法定位到待旋转点,然后把下一个节点设置为新表头,把当前节点设置为表的尾部。
其他:可以和旋转数组放在一起理解
------------
小结:

双指针法不局限于在链表中使用,在许多数组题目和处理字符串的题目里,双指针法的使用可以将时间复杂度下降到O(n).
(例子以后再补充)

3. =====  Reverse=====

[基础题] Reverse Linked List
题目:反转全部链表
思路:维护 pre, cur, next指针。
pre指向当前节点的前驱节点。next指向当前节点的后继节点。

[LC]Reverse Linked List II
题目:反转部分链表,从位置m到位置n.
思路: 首先,找到位置m, 然后进行反转直至到达位置n.

[LC]Swap Nodes in Pair
题目:给定单链表,以2个为一对反转链表 。输入
1->2->3->4 返回 2->1->4->3
思路:维护pre, cur,next指针。Next指向下一个待reverse对的节点。Pre指向已经reverse好的最后一个节点。

[LC]Reverse Nodes in k Group
题目:给定单链表,以k个为单位反转链表
思路:先对已visit的节点计算数量,到达k就把前k个节点reverse.
注意:到达k才reverse, 不到达k不需要。

-------
小结:
反转链表中是一个重要操作。要好好掌握。
LeetCode中虽然没有一个题目要求从头到尾直接反转链表。但是这些题目都是在反转链表这个操作上考的。
最基础的方法,reverse(ListNode head)或 reverse(ListNode head, ListNode pre, ListNode next)一定要能很快且无bug的写出来。

4. =====  Sort=====

[LC]Sort List
题目:在链表中实现排序。要求O(nlogn)
思路:归并 mergesort,双指针(walker/runner)
其他:也可以用其他符合时间的排序操作。

[LC]Insertion Sort List
题目:在链表中实现插入排序
思路:和插入排序一样,双指针(pre/next)
其他:

[LC]Partition List
题目:把链表中小于元素x的节点放在x前,大于x的节点放在x后
思路:和快排 quicksort的Partition操作类似,还用了双指针(walker/runner)。
其他:

[LC]Merge Two Sorted Lists
题目:合并两个有序单链表。
思路:和MergeSort里的Merge操作类似

[LC]Merge k Sorted Lists
题目:合并k个有序单链表并返回1个有序单链表
思路:可以将Merge Two Sorted Lists作为subroutine。使用分治法把k个链表分成两半,然后两两归并,直到最后剩下两个链表就合并结果。
其他:可以用其他数据结构(heap)来优化

-------
小结:
1. 在链表上实现排序,感觉这种题能让大家进一步体会到链表和数组的区别。
2. 合并在链表中是一个典型操作。要好好掌握。类似的题目是一维数组的合并。

=====模拟数值运算=====
[LC]Add Two Numbers
已有讨论帖,
传送门[传送ing]

=====树=====[待总结]
[LC]Convert Sorted List to Binary Tree







本帖被以下淘专辑推荐:

8

主题

3

精华

335

积分

高级会员

Rank: 3Rank: 3

积分
335
发表于 2-17-2016 01:08 AM | 显示全部楼层
转载:
轻松搞定面试中的二叉树题目:http://blog.csdn.net/luckyxiaoqiang/article/details/7518888
轻松搞定面试中的链表题目: http://blog.csdn.net/luckyxiaoqiang/article/details/7393134
回复 支持 1 反对 0

使用道具 举报

10

主题

1

精华

864

积分

超级会员

Rank: 4

积分
864

热心会员推广达人

发表于 2-27-2016 12:06 AM | 显示全部楼层
LL最多考点在增加node和.next处理~ 另外就是处理好general case和special case(NULL, head pointer, tail pointer),各种情况都考虑到~~
回复 支持 1 反对 0

使用道具 举报

5

主题

5

精华

129

积分

版主

Rank: 7Rank: 7Rank: 7

积分
129
发表于 2-17-2016 04:55 AM | 显示全部楼层
嗯,链表题有时候很绕, 还有很多边界情况,或指针设null等trick, 链表题要思路清楚哇,简洁是王道
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表