链表问题
在链表问题中，最常见的方法就是“双指针”，“快慢指针”。
最常用的技巧就是加“fakehead”删除系列
删除链表中的节点 203题（easy）：
删除链表中等于给定值 val 的所有节点。
示例：
输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->4->5
分析：
最基础的删除操作，用到fakehead，定义一个指针一趟遍历，判断指针的下一位是否是目标val。
代码：
public ListNode removeElements(ListNode head, int val) { ListNode i=new ListNode(0); i.next=head; ListNode s=i; while (i.next!=null){ if (i.next.val==val){ i.next=i.next.next; } else i=i.next; } return s.next; } 删除链表中的节点 237题（easy）：
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
示例：
输入: head = [4,5,1,9], node = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
分析：
和203题的区别在于只给了我们这个要被删除的节点，不能像之前一样通过从头节点遍历定位到要被删除的前一节点。所以我们只能操作当前这个节点和他的下一节点，而操作不了他的前一个节点。
思路是把下一节点的值覆盖到当前要被删除的节点上，然后不删除当前节点而是删除下一节点。这样删除的效果的一样的。
代码：
public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } 删除链表的倒数第N个节点 19题：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？分析：
用双指针的方法做；两指针从头节点开始，一个快指针先走n步，然后两个指针同时走，等到快指针走到尾节点时，这时的慢支针就指在倒数第n个节点。注意这里的边界，多试试。
代码：
public ListNode removeNthFromEnd(ListNode head, int n) { if (head==null) return null; ListNode slow=new ListNode(-1); ListNode fast=new ListNode(-1); slow.next=head; fast.next=head; ListNode res=slow; for (int i=0;i 删除排序链表中的重复元素 83题（easy）：
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例：
输入: 1->1->2输出: 1->2
输入: 1->1->2->3->3输出: 1->2->3
分析：
一趟扫描就可以；i挪向下一节点前，看当前节点和它的下一个节点是不是相等；如果相等执行i.next=i.next.next
代码：
public ListNode deleteDuplicates(ListNode head) { if (head==null) return head; ListNode i=head; while (i.next!=null){ if (i.next.val==i.val){ i.next=i.next.next; } else i=i.next; } return head; } 删除排序链表中的重复元素II 82题：
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例：
输入: 1->2->3->3->4->4->5输出: 1->2->5
输入: 1->1->1->2->3输出: 2->3
分析：
（1）这里用到了双指针的方法。一个pre，一个cur
（2）这里的头节点可能被删去，所以操作时在头节点前加一个“假头节点”是必要的。 （3）和I的区别在于只保留没有重复出现的数字，我们要把重复的数字都删掉，因为链表的单向性，要保存一个前驱节点pre。这样才能保证跳过所有重复的数字。代码：
public ListNode deleteDuplicates(ListNode head) { if(head==null) return null; ListNode FakeHead=new ListNode(0); FakeHead.next=head; ListNode pre=FakeHead; ListNode cur=head; while(cur!=null){ while(cur.next!=null&&cur.val==cur.next.val){ cur=cur.next; //有重复cur挪动 } if(pre.next==cur){//成立代表cur没有多挪动跳过重复元素 pre=pre.next; //pre挪动一个 } else{ pre.next=cur.next;//否则连接节点，删掉重复元素 } cur=cur.next;//迭代扫描中cur每次都挪一个 } return FakeHead.next; } 交换旋转反转系列
两两交换链表中的节点 24题：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例：
给定 1->2->3->4, 你应该返回 2->1->4->3.*你的算法只能使用常数的额外空间。*你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
分析：
按要求操作就行 注意加fakehead
代码：
public ListNode swapPairs(ListNode head) { ListNode header=new ListNode(-1); header.next=head; ListNode l=header; while (l.next!=null&&l.next.next!=null){//判断条件注意 ListNode temp1=l.next.next.next; ListNode temp2=l.next; l.next=temp2.next; l.next.next=temp2; temp2.next=temp1; l=l.next.next; } return header.next; } 旋转链表 61题：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例：
输入: 1->2->3->4->5->NULL, k = 2输出: 4->5->1->2->3->NULL解释:向右旋转 1 步: 5->1->2->3->4->NULL向右旋转 2 步: 4->5->1->2->3->NULL
输入: 0->1->2->NULL, k = 4输出: 2->0->1->NULL解释:向右旋转 1 步: 2->0->1->NULL向右旋转 2 步: 1->2->0->NULL向右旋转 3 步: 0->1->2->NULL向右旋转 4 步: 2->0->1->NULL
分析：
1.首先k可能大于节点个数，即k>len,此时旋转的位置是k%len个
2.关键找到旋转后的尾节点tail是哪个节点。观察后发现应该是从头节点数len-k%len个节点 3.最后一步，将原来链表首尾相接成一个环，将旋转后的尾节点tail的后一节点置为NULL 用到双指针（一个确定len，一个确定tail）和fakehead代码：
public ListNode rotateRight(ListNode head, int n) { if (head==null||head.next==null) return head; ListNode dummy=new ListNode(0); dummy.next=head; ListNode fast=dummy,slow=dummy; int i; for (i=0;fast.next!=null;i++)//得到总长度i fast=fast.next; for (int j=i-n%i;j>0;j--) //得到第i-k%i个节点 slow=slow.next; fast.next=dummy.next; //做旋转 dummy.next=slow.next; slow.next=null; return dummy.next;} 反转链表 206题（easy）：
反转一个单链表。
示例：
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
分析：
迭代法一趟遍历，保存当前节点curr的前驱prev和后继nextTemp。
递归法思路一致，传参为nextTemp和prev，递归基是curr==null时，返回它的prev代码：
public ListNode reverseList(ListNode head) { /* 迭代法 */ ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev;} public ListNode reverseList(ListNode head) { /* 递归法*/ return reverseListInt(head, null); } private ListNode reverseListInt(ListNode curr, ListNode prev) { if (curr == null) return prev; ListNode nextTemp = curr.next; curr.next = prev; return reverseListInt(nextTemp, prev); } 反转链表 II 92题：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。示例：
输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL
分析：
思路和I的类似，但是这题是反转m到n的一段，而且要一趟扫描，所以要分段(0～m-1, m, m+1～n)不同处理，额外的变量也是必须的。
下面解法中，m到n这段中定义的subhead实际相当于I中的prev的作用；而这里的pre_cur只是为了将它最后定位在m-1位置上。扫描结束 将pre_cur，subtail，subhead，cur按pre_cur->subhead, subtail->cur接起来.代码：
public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummyhead = new ListNode(0); dummyhead.next = head; ListNode sublisthead = new ListNode(0); ListNode sublisttail = new ListNode(0); int count = 1; ListNode pre_cur = dummyhead, cur = head; while(count <=n){ ListNode temp = cur.next; if (count < m) //这段实际不进行操作，只是保存每次cur的前后两个节点 pre_cur = cur; else if (count == m){ //在m这点上定义 subtail和subhead的指向 sublisttail = cur; sublisthead.next = cur; }else if (count > m){。 //在m+1～n这段上，方法就同I了，subhead就是I中的prev cur.next = sublisthead.next; sublisthead.next = cur; } cur = temp; //cur转向下一节点 ++count; //计数器 } //连接 pre_cur.next = sublisthead.next; sublisttail.next = cur; return dummyhead.next;} 重排链表 143题：
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例：
给定链表 1->2->3->4, 重新排列为 1->4->2->3.给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
分析：
这题用到了反转链表I,可以分为三个步骤来操作：
1.利用快慢指针定位到中间节点（长度为偶数时靠左的中间节点） 2.将后一半reverse 3.将后一半依次交替插入代码：
public void reorderList(ListNode head) { if(head==null||head.next==null) return; //Find the middle of the list ListNode p1=head; ListNode p2=head; while(p2.next!=null&&p2.next.next!=null){ p1=p1.next; p2=p2.next.next; } //Reverse the half after middle 1->2->3->4->5->6 to 1->2->3->6->5->4 Reverse Linked List I ListNode preMiddle=p1; ListNode preCurrent=p1; ListNode current=p1.next; while (current!=null){ ListNode temp=current.next; current.next=preCurrent; preCurrent=current; current=temp; } preMiddle.next.next=null; preMiddle.next=preCurrent; //Start reorder one by one 1->2->3->6->5->4 to 1->6->2->5->3->4 p1=head; p2=preMiddle.next; while(p1!=preMiddle){ preMiddle.next=p2.next; p2.next=p1.next; p1.next=p2; p1=p2.next; p2=preMiddle.next; } } 判断回文链表 234题：
请判断一个链表是否为回文链表。
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？示例：
输入: 1->2输出: false
输入: 1->2->2->1输出: true
分析：
可以用到206题的反转链表来把原链表的后一半反转，然后依次比对。
注意要考虑节点长度为奇数和偶数的两种情况。代码：
public boolean isPalindrome(ListNode head){ ListNode fast=head,slow=head; //快慢指针用法，将slow定位到中间的节点上 while (fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } if (fast!=null){ //fast!=null说明节点总长为奇数 slow=slow.next; } slow=reverseList(slow); fast=head; while (slow!=null){ if (fast.val!=slow.val){ return false; } fast=fast.next; slow=slow.next; } return true; }public ListNode reverseList(ListNode head) { //206题的reverseList函数 ListNode pre=null; while (head!=null){ ListNode next=head.next; head.next=pre; pre=head; head=next; } return pre; } 循环问题
环形链表 141题（easy）：
给定一个链表，判断链表中是否有环。
你能否不使用额外空间解决此题？分析：
这类判断循环的方法就是“快慢指针”，快指针每次两步，慢指针每次一步。如果有循环的话，快慢指针最后一定会汇合。
代码：
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } 环形链表II 142题：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。 进阶：你是否可以不用额外空间解决此题？分析：
这题首先像判断循环一样用快慢指针定位到汇合点，然后就是数学问题了...
假设： 1.L1定义为头点和入口点之间的距离 2.L2定义为入口点和会合点之间的距离 3.C定义为循环的长度 4.n被定义为快速指针绕循环的圈数 则有： 2*（L1+L2）=L1+L2+n*C => L1+L2=n*C =>L1=(n-1)*C+(C-L2) 那么一个指针从头节点，一个指针从汇合点沿着正向每次都只走一步，两指针最后的汇合点就是循环入口点。代码：
public ListNode detectCycle(ListNode head) { if (head==null||head.next==null) return null; ListNode entry=head; ListNode slow=head; ListNode fast=head; while (fast.next!=null&&fast.next.next!=null){ slow=slow.next; fast=fast.next.next; if (slow==fast){ while (entry!=slow){ entry=entry.next; slow=slow.next; } return slow; } } return null;//没有循环 } 其他问题
分割链表 86题：
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。示例：
输入: head = 1->4->3->2->5->2, x = 3输出: 1->2->2->4->3->5
分析：
基本思想是维护两个队列，第一个队列存储val小于x的所有节点，第二个队列存储所有其余节点。 然后连接这两个队列。 请记住将第二个队列的尾部设置为null，否则你将获得Time Limit Exceeded，即有循环
For this list: 5->6->1->2, x=3, at last cur2 points to 6, cur1 points to 2, we must set 6->1 to 6->null, otherwise there will be a cycle.代码：
public ListNode partition(ListNode head, int x) { ListNode d1=new ListNode(-1); ListNode d2=new ListNode(-1); ListNode cur1=d1,cur2=d2; while (head!=null){ if (head.val 相交链表 160题：
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
在节点 c1 开始相交。
注意： 1.如果两个链表没有交点，返回 null. 2.在返回结果后，两个链表仍须保持原有的结构。 3.可假定整个链表结构中没有循环。 4.程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存分析：
这题两个链表的长度可能不一样，所以要先让两个链表各自指针指在“对齐”的位置，然后两指针每次都走一步判断是否相等就能找到相交点。
discuss里有个巧妙的方法，代码如下，记住吧...代码：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //boundary check if(headA == null || headB == null) return null; ListNode a = headA; ListNode b = headB; //if a & b have different len, then we will stop the loop after second iteration while( a != b){ //for the end of first iteration, we just reset the pointer to the head of another linkedlist a = a == null? headB : a.next; b = b == null? headA : b.next; } return a;} 合并两个有序链表 21题：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4输出：1->1->2->3->4->4
分析：
类似于二路归并的思路。
注意这题是通过拼接的方式，不能重新再建一条链表把对应的值存里。代码：
//迭代版本public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode fakehead=new ListNode(-1); ListNode tail=fakehead; while (l1!=null&&l2!=null){ if (l1.val //递归版本 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } if(l2 == null){ return l1; } ListNode mergeHead; if(l1.val < l2.val){ mergeHead = l1; mergeHead.next = mergeTwoLists(l1.next, l2); } else{ mergeHead = l2; mergeHead.next = mergeTwoLists(l1, l2.next); } return mergeHead; } 复制随机指针的链表 138题：
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。//定义的随机指针节点class RandomListNode { int label; RandomListNode next, random; RandomListNode(int x) { this.label = x; }} 分析：
这题和克隆图那道类似，算是那题的一个简化版。使用克隆图那题的BFS方法可以做，但是复杂没必要。这题的一个高票答案只用了三趟扫描，常数空间复杂度。三趟扫描思路如下：
1.在next指针相连的两个节点之间插入一个前一节点的拷贝 如1->2->3->null 插入后为 1->1->2->2->3->3->null 2.这次扫描确定拷贝的节点的random指针指向；因为拷贝的节点就在原节点的后面，所以能够直接定位操作到。 3.再把拷贝的节点从原来的链表中取出来，用next连接起来。代码：
public RandomListNode copyRandomList(RandomListNode head) { RandomListNode iter = head, next; // 第一轮：做好每一个节点的拷贝 // 插入到原连表中 while (iter != null) { next = iter.next; RandomListNode copy = new RandomListNode(iter.label); iter.next = copy; copy.next = next; iter = next; } // 第二轮：标记拷贝节点的random指针指向 iter = head; while (iter != null) { if (iter.random != null) { iter.next.random = iter.random.next; } iter = iter.next.next; } // 第三轮：恢复原链表，把拷贝链表中原链表中取出来。 iter = head; RandomListNode pseudoHead = new RandomListNode(0); RandomListNode copy, copyIter = pseudoHead; while (iter != null) { next = iter.next.next; // 取出拷贝 copy = iter.next; copyIter.next = copy; copyIter = copy; // 恢复原链表 iter.next = next; iter = next; } return pseudoHead.next;} 遗留的题目：
109 有序链表转换二叉搜索树（DFS）
147 对链表进行插入排序（sort） 148 排序链表（sort）