1. 题目：linked-list-cycle
问题描述：判断给定的链表中是否有环,你能给出不利用额外空间的解法么？
检测单链表是否有环一般使用两种解法：
- 解法1：
使用HashMap将换的Node节点放在Map中，若Map的key值有重复的情况下则有环，若从头到尾遍历链表未出现重复的key值，表示没有环。 - 解法2：
使用快慢指针，快指针每次向前走两步，慢指针每次向前走一步，单链表有环时，快指针会与慢指针在同一个位置，表示有环。
2. 题目：linked-list-cycle-ii
问题描述：对于一个给定的链表，返回环的入口节点，如果没有环，返回null，你能给出不利用额外空间的解法么？
解题思路:当判断完当前链表有环之后，先确定环的个数，确定完之后，让前面的指针开始先跑n个节点，然后两支针一起跑，两个指针相等的那个位置就是环形链表的入口节点
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null)//attention
return null;
ListNode fast = head.next;
ListNode slow = head;
int N,i;
while(fast!=slow){
if(fast==null ||fast.next==null)
return null;
else{
slow = slow.next;
fast = fast.next.next;
}
}
for(slow = slow.next, N = 1; slow!=fast; slow=slow.next, N++){}
for(fast = head; N != 0; N--,fast = fast.next){}
for(slow = head; slow!=fast; fast=fast.next, slow=slow.next) {}
return slow;
}
}代码反思：for循环哪怕没有需要在{}中执行的语句，也要写{}，不然编译器会报未知错。养成回头检查的习惯，需不需要在代码入口处先检查指针为null的情况。
3. 题目：sort-list
问题描述：在O(nlogn)的时间内使用常数级空间复杂度对链表进行排序。
解题思路：
- 根据要求nlogn,想到快速排序、归并排序和堆排序，在常用的快排和归并排中，空间复杂度为O(logn)。对于链表结构来说，归并排序比快排更易操作，而链表的排序在归并两个子链表时，不需要像数组实现时建立新的数组存储排序后的序列，故空间复杂度为O(1)。选择Merge Sort处理本题链表结构。
- 归并排序采用分治的思想，算法可分为两部分，分解和合并。一、构造两个已排序的子链表；二、将子链表合并。针对第一部分，可以使用快慢指针的方法，分割链表，然后对分割后的段进行递归排序；针对第二部分，取出两子链表的表头结点进行比较大小，小的先放入新链表。
- 快慢指针*找链表中值：慢指针slow遍历链表，faster指针速度是slow的两倍，则当快指针到达链表结尾时（next节点为空），此时slow指针应该位于链表的中间（链表元素个数是奇数时正中间，偶数应该是一半加1。
注意：快慢指针求中值时，有两种写法，仔细注意其区别及每种写法内部的对应关系，避免出错。public ListNode getMid(ListNode head){ if(head == null || head.next == null){ return head; } ListNode slow = head; ListNode fast = head;//attention while(fast.next != null && fast.next.next != null){ //attention slow = slow.next; fast = fast.next.next; } return slow; }public ListNode getMid(ListNode head){ if(head == null || head.next == null){ return head; } ListNode slow = head; ListNode fast = head.next;//attention while(fast != null && fast.next != null){//attention slow = slow.next; fast = fast.next.next; } return slow; }
4. 题目：copy-list-with-random-pointer
问题描述：现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。请对这个链表进行深拷贝。
解题思路：首先，深拷贝即新链表的每个结点有新的不同于原链表结点的新地址进行存储。
1、我们可以将创建的新节点并插入放在老节点的后面，让他们串起来
2、创建成功后现在根据原有的链表就可以很方便的复制随机指针了
3、最后将我们的链表分离出来，就得到了所求的链表
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null)
return null;
RandomListNode cur = head;
RandomListNode cur_C = head;
do{
RandomListNode newnode = new RandomListNode(0);
newnode.label = cur.label;
cur_C = newnode;
cur_C.next = cur.next;
cur.next = cur_C;
cur = cur_C.next;
}while(cur!=null);
cur = head;
RandomListNode ptr = head;
//第二遍扫描：根据原结点的random，给新结点的random赋值
RandomListNode node = head;
while (node != null) {
if (node.random != null) node.next.random = node.random.next;
node = node.next.next;
}
RandomListNode newhead = head.next;
//第三遍扫描：把新结点从原链表中拆分出来
node = head;
while (node != null) {
RandomListNode newnode = node.next;
node.next = newnode.next;
if (newnode.next != null) newnode.next = newnode.next.next;
node = node.next;
}
return newhead;
}
}代码反思：解题思路要明确1、2、3步，代码也要思路清晰同时易于阅读。一开始我把2、3部分揉在了一起，最后出错看不出问题在哪。代码追求简洁从来不是将解题步骤两步并做一步，而是在每一步的具体环节中选择更高效简洁的方法。
5. 题目：reverse-linked-list-ii
问题描述：
将一个链表m位置到n位置之间的区间反转，要求使用原地算法，并且在一次扫描之内完成反转。
例如：
给出的链表为1->2->3->4->5->NULL, m = 2 ，n = 4,
返回1->4->3->2->5->NULL.
注意：
给出的m，n满足以下条件： 1 ≤ m ≤ n ≤ 链表长度
解题思路：想到链表的倒序可以用建立链表的“头插法”思想来完成，具体到本题，可分为三个步骤：
1.从前向后扫描链表，找到需要reverse的起始位置，第m个结点。
2.记录位置m-1,从第m+1个结点开始插入到m-1结点之后。
3.继续向下操作第m+2个结点，直到n。
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head==null || head.next==null)
return head;
//在head之前生成新的头结点，应对m = 1的情况
ListNode newhead = new ListNode(-65535);
newhead.next = head;
ListNode position_pre = newhead;
ListNode ptr_pre = newhead;
ListNode ptr_cur = head;
int i = 1;
while(i < m){//找到m
position_pre = position_pre.next;
ptr_pre = ptr_pre.next;
ptr_cur = ptr_cur.next;
i++;
}
ptr_pre = ptr_pre.next;
ptr_cur = ptr_cur.next;
i++;
for( ; i<=n; i++){//开始在pre之后进行插入
ptr_pre.next = ptr_cur.next;
ptr_cur.next = position_pre.next;
position_pre.next = ptr_cur;
//调整进行下一个结点
ptr_cur = ptr_pre.next;
}
return newhead.next;
}在题解中看到了更简洁的写法，学习一下。
链接：https://www.nowcoder.com/questionTerminal/b58434e200a648c589ca2063f1faf58c
来源：牛客网
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode preStart = dummy;
ListNode start = head;
for (int i = 1; i < m; i ++ ) {
preStart = start;
start = start.next;
}
// reverse
for (int i = 0; i < n - m; i ++ ) {
ListNode temp = start.next;
start.next = temp.next;
temp.next = preStart.next;
preStart.next = temp;
}
return dummy.next;
}
}6. 题目：reorder-list
问题描述：
将给定的单链表L： L 0→L 1→…→L n-1→L n,
重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…
要求使用原地算法，并且不改变节点的值
例如：对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.
解题思路：由于数据结构是单向链表而非双向链表，所以思考将从后向前的扫描过程转化为从前向后，刚好刚实现了reverse函数，此处刚好可以用到。过程总体可分为两步：
1.将后半部分链表倒置
2.两组指针分别从表头和倒置的表头向后扫描，将后者向前插入
public class Solution {
public void reorderList(ListNode head) {
if( head==null || head.next==null )
return;
int count = 0;
ListNode node = head;
//后半部分reverse
while(node!=null){
count++;
node = node.next;
}
int begin = count/2+1;
reverseBetween(head,begin,count);
//从头扫描进行节点插入
ListNode tr1 = head;
while(begin > 2) {
tr1 = tr1.next;//node为begin的前驱
begin--;
}
ListNode pr1 = head;
ListNode tr2 = tr1.next;
while(pr1!=null && pr1.next!=null && tr2!=null){
//先摘出
tr1.next = tr2.next;
//tr2 插入到pr1 pr2之间
tr2.next = pr1.next;
pr1.next = tr2;
//下一个
pr1 = pr1.next.next;
tr2 = tr1.next;
}
}
public static ListNode reverseBetween(ListNode head, int m, int n) {}
//用到上一题实现的reverse函数
}代码反思：第二步在实现过程中比较复杂，遇到这种情况先写好注释理清细节思路，再在框架下填代码。
7. 题目：partition-list
问题描述：
给出一个链表和一个值x，以x为参照将链表划分成两部分，使所有小于x的节点都位于大于或等于x的节点之前。两个部分之内的节点之间要保持的原始相对顺序。
例如：给出1->4->3->2->5->2和x = 3,
返回1->2->2->4->3->5.
解题思路：首先拿到问题联想到快排中的轴枢分割序列的方法，需要在链表中找到一个轴枢x，再从左到右扫描将所有小于x的结点丢到左边。通过观察题目描述，发现>=x的结点相对顺序也没有变。所以轴枢不能随便选，应选从左到右第一个大于等于x的结点，这样就免去了遇到大的要丢到右边的情况也就不会改变右侧结点的相对顺序。算法整体分为三个步骤：（括号中是需要思考检查的特殊情况）
1.从头扫描链表，拿到第一个大于等于x的结点pivot；
（ps. pivot没找到的情况）
2.生成新表头，pivot放在newhead之后head之前；
（ps. pivot本身即是头结点的情况）
3.从pivot的下一个结点开始扫描，将需要移动结点插入到pivot之前。
（ps. 只有pivot一个结点的特殊情况）
public ListNode partition(ListNode head, int x) {
if(head==null)
return head;
ListNode newhead = new ListNode(0);
newhead.next = head;
ListNode pre = newhead;
ListNode pivot = head;
//找到第一个 >=x 的结点作为枢轴pivot,放到表头
while(pivot!=null && pivot.val<x){
pre = pre.next;
pivot = pivot.next;
}
if(pivot==null)
return newhead.next;
pre.next = pivot.next;
if(pivot!=head)
pivot.next = head;
newhead.next = pivot;
pre = newhead;
//从头开始循环将 <x 的结点插入到 pre pivot 之间
ListNode pr = pivot;
ListNode tr = pr.next;
while(tr!=null){
if(tr.val < x){//遇到需调整节点
pr.next = tr.next;//摘
tr.next = pivot;//插
pre.next = tr;
pre = pre.next;//下一个
tr = pr.next;
}
else{
pr = pr.next;
tr = tr.next;
}
}
return newhead.next;
}代码反思：每次都希望能在网页中写，不用IDE调试，但总是循环出错，可见要特意关注检查循环结束条件，如同程序入口检查head==null head.next==null对程序步骤开始的影响一样，进而养成逐步辩证思考排查漏洞的思维能力。
对于练习场景中无法知道问题来源、无法得知自己的代码究竟在什么样的测试样例下出了问题，以往是通过测试样例来排查代码中的漏洞。才发现有思路还不够，还要逻辑严谨才行，这才是刷题真正的目的吧，今日顿悟哇。
题外话：看了讨论中别人给出的题解，绝大多数是将原链表分成两个再合并，我觉得自己的思路很巧妙啊！
8. 题目： remove-duplicates-from-sorted-list
问题描述：
删除给出链表中的重复元素，使链表中的所有元素都只出现一次
例如：
给出的链表为1->1->2,返回1->2.
给出的链表为1->1->2->3->3,返回1->2->3.
解题思路：题目中val的范围没有明确给出。先采用简单思路，将链表的val值对应到一个hashmap来保证每个值只出现一次。对于负值本懒人也用了最简单无脑的hash函数，以牺牲空间为代价。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null)
return head;
int[] hashmap = new int[131070];
for(int i = 0; i<131070; i++)
hashmap[i] = 0;
ListNode node = head;
ListNode newhead = new ListNode(-1);
newhead.next = head;
ListNode pre = newhead;
while(node!=null){
if(hashmap[this.getHashNum(node.val)]==0){
hashmap[this.getHashNum(node.val)] = 1;
pre = pre.next;
node = node.next;
}
else{
pre.next = node.next;
node = pre.next;
}
}
return newhead.next;
}
public static int getHashNum(int val){
if(val < 0) {
return val+65535;
}
else
return val;
}
}通过后看了其他人通过本题的代码，大家的代码很短，只考虑了重复结点相邻的情况，题目中没有明说然而也能通过所有样例，还是ACM的题目严谨啊。
9. 题目：remove-duplicates-from-sorted-list-ii
问题描述：
在上一题基础上，将有重复的元素的结点全部删去，而不是保留一个。
解题思路：沿用上一题思路，做小小改动，代码思想同上。
10. 题目：remove-duplicates-from-sorted-list-ii
问题描述：
给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）
解题思路：总体分为两步：
1.找到中间结点length/2(中间偏左结点)，以其next作为当下子树的根节点
2.将链表一分为二，递归建立左右子树
public TreeNode sortedListToBST(ListNode head) {
//退出条件
if(head==null) return null;
if(head.next==null) return new TreeNode(head.val);
ListNode fast = head.next, slow = head;
//find mid
for(; fast.next!=null && fast.next.next!=null; slow = slow.next,fast = fast.next.next);//mid = slow.next
//处理根节点
TreeNode root = new TreeNode(slow.next.val);
//先建立右子树，再从中间断掉链表
root.right = sortedListToBST(slow.next.next);
slow.next = null;
//递归建立左子树
root.left = sortedListToBST(head);
return root;
}代码反思：调整slow fast的过程中一定要非常明确自己要的是哪一个节点，稍有偏差，就无法得到正确的结果
京公网安备 11010502036488号