链表题目重要顺序分类:
2 两数相加(ok)
21. 合并两个有序链表(ok) 链表 【类似于题2】
24 : 链表交换
92: 反转链表 II (特别重要,比较难)
剑指offer:
24:反转链表
25:合并链表
52:2个链表第一个公共节点
第2等级:
23: 合并K个升序链表
141: 环形链表
142: 环形链表2
148: 排序链表
160: 相交链表
143: 重排链表
19: 删除链表的倒数第 N 个结点
25: K 个一组翻转链表
总结:递归,快慢指针比较
链表的6大题型:删除,合并,反转,环形,排序, 翻转, 想加
链表题目分类:第一类: 删除类-----------快慢指针
19: 删除链表的倒数第 N 个结点 链表
public ListNoderemoveNthFromEnd(ListNode head, int n) {
// n并不知道，只有遍历完成才能得到
ListNode dummy =new ListNode(0, head); // 生成一个0开始的dummy节点
ListNode first = head;
ListNode second = dummy;
for (int i =0; i < n; ++i) {// 先把快指针移动n。移动到了3的位置
first = first.next;
}
while (first !=null) {// 一直遍历到快指针结束
first = first.next; // 为什么要移动这个？？？？因为这个才会移动链表，或者是遍历链表
second = second.next;
}
second.next = second.next.next;// 下一个节点直接指向下下个
ListNode ans = dummy.next;// 因为要返回头节点
return ans;
}
删除有序/无序链表中重复的元素(并不重要)
leetcode 83
第二类: 合并链表(21,23)------递归
例题：21 Merge Two Sorted Lists 【easy】
题意：将两个排序好的链表合并成新的有序链表
public ListNodemergeTwoListsDigui(ListNode list1, ListNode list2) {
if (list1 ==null) {
return list2;
}
if (list2 ==null)return list1;
if (list1.val > list2.val) {// l2小
list2.next = mergeTwoListsDigui(list2.next, list1); // 下一个元素是：自己的下一个和大的元素比较
return list2;
}else {// l1 小
list1.next = mergeTwoListsDigui(list1.next, list2); // 下一个元素是：自己的下一个和大的元素比较
return list1;
}
}
第三类: 翻转类题型-------递归
最基础最常在面试中遇到的提醒，206一定要熟练掌握
/***
* 递归的方式反转链表
* 1.递归依次返回的数据
* 2。下下个指向自己
* @param head
* @return
*/
public ListNodereverseListDigui(ListNode head) {
if (head ==null || head.next ==null) {
return head;
}
ListNode res = reverseListDigui(head.next); // res=5 head=4
head.next.next = head; // 4->5->null变成4->5->4
head.next =null;// 4->null
return res;
}
翻转部分单链表---92(用到206题)
public ListNodereverseBetween(ListNode head, int left, int right) {
ListNode dummyNode =new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
for (int i =0; i < left -1; i++) {
pre = pre.next;
}
ListNode rightNode = pre;
for (int i =0; i < right - left +1; i++) {
rightNode = rightNode.next;
}
ListNode leftNode = pre.next;
ListNode curr = rightNode.next;
pre.next =null;
rightNode.next =null;
reverseLinkedList(leftNode);
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
}
/***
* 206题，递归的方式反转链表
* @param head
*/
public void reverseLinkedList(ListNode head) {
// 也可以使用递归反转一个链表
ListNode pre =null;
ListNode cur = head;
while (cur !=null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
25:
public ListNodereverseKGroup(ListNode head, int k) {
ListNode dummy =new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next !=null) {
for (int i =0; i < k && end !=null; i++) end = end.next;
if (end ==null)break;
ListNode start = pre.next;
ListNode next = end.next;
end.next =null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dummy.next;
}
/**
* 206
* @param head
* @return
*/
private ListNodereverse(ListNode head) {
ListNode pre =null;
ListNode curr = head;
while (curr !=null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
第四类: 环形链表------快慢指针
例题：141 Linked List Cycle 【easy】
例题：142 Linked List Cycle 【easy】
public ListNodedetectCycle(ListNode head) {
if (head ==null || head.next ==null) {
return null;
}
ListNode fast = head, slow = head;
// step1: 快慢指针一起走，指针碰头快回头
while (fast !=null && fast.next !=null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast ==null || fast.next ==null) {
return null;
}
fast = head;
// step2:一步一步走，再相遇就是goal
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
相交链表: 相交链表(160)
public ListNodegetIntersectionNode(ListNode headA, ListNode headB) {
if (headA ==null || headB ==null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA ==null ? headB : pA.next; // 写法，pA = pA == null
pB = pB ==null ? headA : pB.next;
}
return pA;
}
第六类:排序链表
143
public void reorderList(ListNode head) {
if (head ==null) {
return;
}
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next =null;
l2 = reverseList(l2);
mergeList(l1, l2);
}
public ListNodemiddleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next !=null && fast.next.next !=null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNodereverseList(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 void mergeList(ListNode l1, ListNode l2) {
ListNode l1_tmp;
ListNode l2_tmp;
while (l1 !=null && l2 !=null) {
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
148:(用到21题)
public ListNodesortList(ListNode head) {
return sortList(head, null);
}
private ListNodesortList(ListNode head, ListNode tail) {
if (head ==null) {
return head;
}
if (head.next == tail) {
head.next =null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode listNode1 = sortList(head, mid);
ListNode listNode2 = sortList(mid, tail);
ListNode sorted = merge(listNode1, listNode2);
return sorted;
}
private ListNodemerge(ListNode list1, ListNode list2) {
if (list1 ==null) {
return list2;
}
if (list2 ==null)return list1;
if (list1.val > list2.val) {// l2小
list2.next = merge(list2.next, list1); // 下一个元素是：自己的下一个和大的元素比较
return list2;
}else {// l1 小
list1.next = merge(list1.next, list2); // 下一个元素是：自己的下一个和大的元素比较
return list1;
}
}
回文链表: 234
public boolean isPalindrome(ListNode head) {
if (head ==null) {
return true;
}
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result =true;
while (result && p2 !=null) {
if (p1.val != p2.val) {
result =false;
}
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNodereverseList(ListNode head) {
ListNode prev =null;
ListNode curr = head;
while (curr !=null) {
ListNode nextTemp = curr.next;
curr.next = prev; // 交换
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNodeendOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next !=null && fast.next.next !=null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
第七类:拆分链表
例题：86 Partition List 【medium】
题意：给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。
test case:
解题思路: 二分法。设置两个指针left和right，顺序遍历整条链表，left、mid、target三者比较，根据情况left右移或者right左移。关键就在于边界情况和元素有重复。
当 nums[mid] = nums[left] 时，这时由于很难判断 target 会落在哪，那么只能采取 left++
当 nums[mid] > nums[left] 时，这时可以分为两种情况，判断左半部比较简单
当 nums[mid] < nums[left] 时，这时可以分为两种情况，判断右半部比较简单
code
链表:(单链表：反转、插入、删除)
基础知识：链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是O（1），查找任意元素位置O（N）
基础题目：
Leetcode 206. Reverse Linked List
Leetcode 876. Middle of the Linked List
注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。
第8类:链表相加求和
题目： 假设链表中每一个节点的值都在 0-9 之间，那么链表整体可以代表一个整数。 例如： 9->3->7 可以代表 937 给定两个这样的链表，头节点为 head1 head2 生成链表相加的新链表。 如 9->3->7 和 6 -> 3 生成的新链表应为 1 -> 0 -> 0 -> 0
总结链表: 基本操作:反转链表,合并一个链表,找链表的中间节点. 删除一个节点,添加一个节点.
采用的方法:递归,快慢指针,迭代法
如何判断一个单链表有环？链表翻转；
链表每 k 位逆序；
K个一组反转链表（重点）
链表反转
算法题：两个有序链表合并
6.算法题，链表求和
链表表示一个数字，求两个数字相加之和，返回一个链表
算法题：给定一个链表L1、L2,每个元素是为10以内的正整数，链表表示一个数字，表头为高位。 求两个链表之差，以链表形式返回
给定两个链表，存储着两个16进制数，链表的一个节点存储着16进制数的其中一个数，从高位到低位，求相加的值，返回一个链表，链表中保存相加的结果。(先反转链表，然后逐位相加，记录进位值，再与高位相加)手写代码
判断单链表相交，找出节点，手写代码
算法题：查找单链表中倒数第k个节点
从长序列中找出前K大的数字
算法题：冒泡排序的链表实现
链表逆序(头条几乎是必考的)
public ListNode reverseList(ListNode head) { if (head== null) { return null;} if (head.next== null) { return head;} ListNodeprev= null;ListNodecurrent= head;while (current != null) { ListNodenext= current.next;current.next= prev;prev= current;current= next;} return prev;}复制代码
删除排序数组中的重复项
public int removeDuplicates(int[]nums) { intlength= nums.length;if (length==0|| length ==1) { return length;} intsize=1;intpre= nums[0];for (inti=1; i < length; ){ if (nums[i]== pre) { i++;} else {pre= nums[size++] = nums[i++];} } return size;}复制代码
数组中找到重复元素
n个长为n的有序数组，求最大的n个数
用O(1)的时间复杂度删除单链表中的某个节点 把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素,只有删除最后一个元素的时间为o(N)平均时间复杂度仍然为O(1)
public void deleteNode(ListNode node) { ListNodenext= node.next;node.val= next.val;node.next= next.next;}复制代码
删除单链表的倒数第N个元素 两个指针,第一个先走N步第二个再走,时间复杂度为O(N),参考link
public ListNode removeNthFromEnd(ListNode head, int n) { if (head== null) { return null;} if (head.next== null) { returnn==1? null : head;} intsize=0;ListNodepoint= head;ListNodenode= head;do { if (size >= n + 1) {point= point.next;}node= node.next;size++;} while (node != null);if (size== n) { return head.next;}node= point.next;point.next= node == null ? null : node.next;return head;}复制代码
从长序列中找出前K大的数字
用数组实现双头栈
publicstaticclass Stack<T>{ public Stack(intcap) { if (cap<=0) { thrownewIllegalArgumentException(); }array=newObject[cap];left=0;right=cap-1; } private Object[]array; privateintleft; privateintright; public void push1(T val) {intindex=left+1; if (index<right) {array[index]=val; }left=index; }@SuppressWarnings("unchecked") public T pop1() { if (left>0) {return(T)array[left--];}returnnull; } public void push2(T val) {intindex=right-1; if (index>left) {array[index]=val; }right=index; }@SuppressWarnings("unchecked") public T pop2() { if (right<array.length) {return(T)array[right++]; }returnnull; } }复制代码
两个链表求和，返回结果也用链表表示 1 -> 2 -> 3 + 2 -> 3 -> 4 = 3 -> 5 -> 7
public ListNode addTwoNumbers(ListNode node1, ListNode node2) { ListNodehead= null;ListNodetail= null;booleanupAdd=false;while (!(node1== null && node2 == null)) { ListNodemidResult= null;if (node1 != null) {midResult= node1;node1= node1.next;} if (node2 != null) { if (midResult== null) {midResult= node2;} else { midResult.val += node2.val;}node2= node2.next;} if (upAdd) { midResult.val += 1;} if (midResult.val >= 10) {upAdd=true;midResult.val %= 10;} else {upAdd=false;} if (head== null) {head= midResult;tail= midResult;} else {tail.next= midResult;tail= midResult;} } if (upAdd) {tail.next= new ListNode(1);} return head;}复制代码
交换链表两两节点
public ListNode swapPairs(ListNode head) { if (head== null) { return null;} if (head.next== null) { return head;} ListNodecurrent= head;ListNodeafter= current.next;ListNode nextCurrent;head= after;do {nextCurrent= after.next;after.next= current;if (nextCurrent== null) {current.next= null;break;}current.next= nextCurrent.next;after= nextCurrent.next;if (after== null) {current.next= nextCurrent;break;}current= nextCurrent;} while (true);return head;}复制代码
找出数组中和为给定值的两个元素，如：[1, 2, 3, 4, 5]中找出和为6的两个元素。
public int[]twoSum(int[]mun,int target) { Maptable= new HashMap<>();for (inti=0; i < mun.length; ++i){ Integervalue= table.get(target - mun[i]);if (value != null) { return new int[]{i, value};} table.put(mun[i], i);} return null;}
单链表的基本操作(增删改查)
获取单链表的长度
public int getLength(Node head){
if(head ==null){
return 0;
}
int len =0;
while(head !=null){
len++;
head = head.next;
}
return len;
}
查询指定索引的节点值或指定值得节点值的索引
/** 获取指定角标的节点值 */
public int getValueOfIndex(Node head, int index)throws Exception {
if (index <0 || index >= getLength(head)) {
throw new Exception("角标越界！");
}
if (head ==null) {
throw new Exception("当前链表为空！");
}
Node dummyHead = head;
while (dummyHead.next !=null && index >0) {
dummyHead = dummyHead.next;
index--;
}
return dummyHead.value;
}
/** 获取节点值等于 value 的第一个元素角标 */
public int getNodeIndex(Node head, int value) {
int index = -1;
Node dummyHead = head;
while (dummyHead !=null) {
index++;
if (dummyHead.value == value) {
return index;
}
dummyHead = dummyHead.next;
}
return -1;
}
链表添加一个元素
头部添加一个元素
public NodeaddAtHead(Node head, int value){
Node newHead =new Node(value);
newHead.next = head;
return newHead;
}
尾部添加一个元素
public void addAtTail(Node head, int value){
Node node =new Node(value);
Node dummyHead = head;
//找到未节点 注意这里是当元素的下一个元素为空的时候这个节点即为未节点
while( dummyHead.next !=null){
dummyHead = dummyHead.next;
}
dummyHead.next = node;
}
链表删除一个元素
由单链表的增加删除可以看出，链表的想要对指定索引进行操作（增加，删除），的时候必须获取该索引的前一个元素。记住这句话，对链表算法题很有用。
public NodedeleteElement(Node head, int index)throws Exception {
int size = getLength(head);
if (index <0 || index >= size) {
throw new Exception("角标越界！");
}
if (index ==0) {
return deleteHead(head);
}else if (index == size -1) {
deleteTail(head);
}else {
Node pre = head;
while (pre.next !=null && index >1) {
pre = pre.next;
index--;
}
//循环结束后 pre 保存的是索引的上一个节点 将其指向索引的下一个元素
if (pre.next !=null) {
pre.next = pre.next.next;
}
}
return head;
}
寻找单链表的中间元素:快慢指针 (类似于判读一个链表是否有环)----题目(143)归并排序
已知一个单链表求倒数第 N 个节点()
常用技巧
1.使用dummy node。dummy node就是在链表的head前加一个节点指向head，即dummy->head，可以理解成一个虚拟节点。多针对于单链表没有前向指针的问题，保证链表的head不会在删除操作中丢失。通常情况下，如果链表的head会发生变化，譬如删除或者被修改等，可以创建dummy node：
ListNodedummy=newListNode(0);dummy.next = head;复制代码
这样就使得操作head节点与操作其他节点没有区别。
2.双指针法。对于寻找链表的某个特定位置，或者判断是否有环等问题时，可以用两个指针变量fast和slow:
ListNodeslow=head;ListNodefast=head;复制代码
以不同的速度遍历该链表，以找到目标位置。注意：在测试时，需要分别选取链表长度为奇数和偶数的test case，可以验证算法在一般情况下的正确性避免遗漏。
3.交换节点的处理。如果需要交换两个节点的位置，譬如24题 Swap Nodes in Pairs,需要交换两个相邻位置的节点，对于这两个前驱节点，他们的next指针会受到影响，这两个节点本身也会受到影响，可以用以下步骤：
1）先交换两个前驱节点的next指针的值
2）再交换这两个节点的next指针的值
无论这两个节点的相对位置和绝对位置如何，以上的处理方式均可成立
4.同时操作两个链表的处理。遇到这种题目，循环的条件一般可以用while（list1 && list2），当循环跳出来后，再处理剩下非空的链表，这相当于：边界情况特殊处理，常规情况常规处理
链表的问题是面试当中常常会问到的，比如链表的倒置，删除链表中某个结点，合并两个排序链表，合并 k 个排序链表，排序两个无序链表等。
这些题目一般有一些相应的技巧可以解决。
第一，引入哨兵结点。如我们开头说的 dummy node 结点。在任何时候，不管链表是不是空，head结点都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫做带头链表。
第二，双指针法。这种用法适用于查找链表中某个位置，判断链表是否有环等
第三，分之归并法。这种用法适用于链表的排序处理，如合并 k 个排序链表，排序两个无序链表等。
第四，在解答的过程中，要多考虑边界情况。
链表为空
链表中只有一个结点
链表中只包含两个结点
代码在处理头结点跟尾结点是否存在什么问题
链表的相关重要的操作：
1.dummo：添加头节点。 因为会移动链表。所以要有一个保存最开始的
2.pr-->node
3.next-->node
如何移动指针
特点：没有指向前面的指针,所以需要定义一个pre
最后返回dummy .next()。就是链表
链表的一些操作：
1.如何遍历一个链表
while (head !=null) {
head=head.next;
}
2.如何指向下一个指针
head=head.next;区别：
// head.next = head.next.next;
// head=head.next;
链表专项突破
