h
hexinyuan

# 1. dummy node

• remove duplicates from sorted list
• remove duplicates from sorted list ii (***)
• swap two nodes in linked list
• reverse linked list ii （找到prem和postn,然后翻转指定的部分）
• merge two sorted list
• partition list (两个list，一个存放小的一个存放大的，然后将两个链表连起来,注意将大的末尾的next置为空) dummyNode.next = head 回收dummyNode：ret = dummyNode.next dummyNode = null

# 2. basic skills

• insert a node in sorted list
• remove a node from linked list
• find the middle of a linked list
• merge two sorted list

# 3. fast&slow pointers

• find the middle of linked list
• linked list cycle ii （相遇后，slow指针回到原点，然后slow和fast各走一步，会在入口处相遇）

# 4. demo

• merge k sorted list
• odd even linked list (***)
• reorder list (1.快慢指针找中点 2.后半部分revers 3.合并两个链表) (与palindrome linked list类似)
• rotate list
• insertion sort list(链表插入排序)
• sort list(1.快慢指针找中点 2.归并排序)
• convert sorted list to bst
• reverse nodes in k group
• delete node in linked list(思路：把要删除节点的next的值赋给该节点，然后删除next，注意两个特殊情况node==null 和 node.next == null)
• remove nth node from end of list(两根指针p,q,让q想走n+1步，然后pq同时走，当q走到null的时候，p刚好走到要删除节点的上一个位置，注意：非空判断)
• copy list with random pointer （1.复制 2.复制random 3.断开返回复制出来的）

``````
public class Solution {
public ListNode removeElements(ListNode head, int val) {
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
return ret;
}
}
``````

## remove a node from sorted list

``````
public class Solution {
return null;
}

while (node.next != null) {
if (node.val == node.next.val) {
node.next = node.next.next;
} else {
node = node.next;
}
}
}
}
``````

## remove a node from sorted list ii (note)

1->2->3->3->4->4->5, return 1->2->5. 1->1->1->2->3, return 2->3.

``````

public class Solution {

ListNode dummy = new ListNode(0);
ListNode cur = dummy;

while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int val = cur.next.val;
while (cur.next != null && cur.next.val == val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}

return dummy.next;
}
}
``````

## swap two nodes in linked list

``````
public class Solution {
public ListNode swapNodes(ListNode head, int v1, int v2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
ListNode p=null,q = null;

while (cur != null && cur.next != null) {
if (cur.next.val == v1) {
p = cur;
} else if (cur.next.val == v2) {
q = cur;
}
if (p != null &&  q != null) {
break;
}
cur = cur.next;
}

if (p != null && q != null) {
if (p.next == q) {
ListNode nextQ = q.next;
p.next = nextQ;
q.next = nextQ.next;
nextQ.next = q;
} else if (q.next == p) {
ListNode nextP = p.next;
q.next = nextP;
p.next = nextP.next;
nextP.next = p;
} else {
ListNode nextP = p.next;
ListNode nextNextP = nextP.next;
ListNode nextQ = q.next;
p.next = q.next;
q.next = nextP;
nextP.next = nextQ.next;
nextQ.next = nextNextP;
}
}
return dummy.next;
}
}
``````

``````
return null;
}

ListNode prev = null;

while (cur != null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}

``````

hint:找到prem和postn，然后翻转

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

``````
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m >= n || head == null) {
}

ListNode dummy = new ListNode(0);

for (int i = 1; i < m; i++) {
return null;
}
}

ListNode nNode = mNode, postnNode = mNode.next;
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;
premNode.next = nNode;

return dummy.next;
}
}
``````

## merge two sorted list

``````
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode lastNode = dummy;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}

if (l1 != null) {
lastNode.next = l1;
} else {
lastNode.next = l2;
}

return dummy.next;
}
}
``````

## partition list

``````

public class Solution {
public ListNode partition(ListNode head, int x) {
return null;
}

ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy, right = rightDummy;

} else {
}
}

right.next = null;
left.next = rightDummy.next;
return leftDummy.next;
}
}
``````

## find the midddle

1 2 3 4 5 s f s f s f
1 2 3 4 5 6 s f s f s f

``````
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

``````

``````
public class Solution {
return false;
}

ListNode fast, slow;
while (fast != slow) {
if(fast==null || fast.next==null)
return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}
``````

1. 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

2. 在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

3. 如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

``````

public class Solution {
return null;
}

ListNode fast, slow;
while (fast != slow) {
if(fast==null || fast.next==null)
return null;
fast = fast.next.next;
slow = slow.next;
}

slow = slow.next;
}
}
}

``````

## merge k sorted list

``````
public class Solution {

public ListNode mergeKLists(List<ListNode> lists) {
if (lists.size() == 0) {
return null;
}
return mergeHelper(lists, 0, lists.size() - 1);
}

private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
if (start == end) {
return lists.get(start);
}

int mid = start + (end - start) / 2;
ListNode left = mergeHelper(lists, start, mid);
ListNode right = mergeHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
tail = list1;
list1 = list1.next;
} else {
tail.next = list2;
tail = list2;
list2 = list2.next;
}
}
if (list1 != null) {
tail.next = list1;
} else {
tail.next = list2;
}

return dummy.next;
}
}
``````

heap

``````
public class Solution {
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
public int compare(ListNode left, ListNode right) {
return left.val - right.val;
}
};

public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}

Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) {
}
}

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
}
}
return dummy.next;
}
}

``````

``````

public class Solution {
return true;
}

middle.next = reverse(middle.next);

ListNode p1 = head, p2 = middle.next;
while (p1 != null && p2 != null && p1.val == p2.val) {
p1 = p1.next;
p2 = p2.next;
}

return p2 == null;
}

return null;
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

ListNode prev = null;

}

return prev;
}
}
``````

``````
public class Solution {
while(odd.next != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
}
}
``````

## reorder list

``````
public class Solution {
return;
}
//1.找到中点
//2.反转后半部分
middle.next = reverse(middle);
//3.合并两个部分
ListNode right = middle.next;
}

private ListNode findMiddle(ListNode node) {
ListNode slow = node;
ListNode fast = node.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

private ListNode reverse(ListNode pre) {
ListNode cur = pre.next;
ListNode curPost  = null;
if (cur != null) {
curPost = cur.next;
while (cur != null && curPost != null) {
ListNode temp = curPost.next;
curPost.next  = cur;
cur = curPost;
curPost = temp;
}
pre.next.next = curPost;
pre.next = cur;
}
return pre.next;
}

private ListNode merge(ListNode left, ListNode right, ListNode middle) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;

while (right != null) {
tail.next = left;
tail = tail.next;
left  = left.next;

tail.next = right;
tail = tail.next;
right = right.next;
}

if (left == middle) {
tail.next = left;
tail = tail.next;
}
tail.next = null;
return dummy.next;
}
}

``````
``````

//Find the middle of the list
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
ListNode preMiddle=p1;
ListNode preCurrent=p1.next;
while(preCurrent.next!=null){
ListNode current=preCurrent.next;
preCurrent.next=current.next;
current.next=preMiddle.next;
preMiddle.next=current;
}

//Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
p2=preMiddle.next;
while(p1!=preMiddle){
preMiddle.next=p2.next;
p2.next=p1.next;
p1.next=p2;
p1=p2.next;
p2=preMiddle.next;
}
}
``````

## rotate list

``````
public class Solution {
int length = 0;
length ++;
}
return length;
}

public ListNode rotateRight(ListNode head, int n) {
return null;
}

n = n % length;

ListNode dummy = new ListNode(0);

ListNode tail = dummy;
for (int i = 0; i < n; i++) {
}

tail = tail.next;
}

dummy.next = tail.next;
tail.next = null;
return dummy.next;
}
}
``````

## insertion sort list (****)

``````

public class Solution {
ListNode dummy = new ListNode(Integer.MIN_VALUE);
while (cur != null){
ListNode pos = findInsertPos(dummy, cur.val);
ListNode tmp = cur.next; //记录当前遍历节点的下一个节点，以便继续遍历下个节点
cur.next = pos.next;
pos.next = cur;
cur = tmp;
}
return dummy.next;
}

//找到当前遍历点cur的插入位置
private ListNode  findInsertPos(ListNode head, int x){
ListNode  pre = null;
while (cur != null && cur.val <= x){
pre = cur;
cur = cur.next;
}
return pre;
}
}

``````

## sort list

``````// version 1: Merge Sort
public class Solution {
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
} else {
}
tail = tail.next;
}
} else {
}

return dummy.next;
}

}

ListNode right = sortList(mid.next);
mid.next = null;

return merge(left, right);
}
}

// version 2: Quick Sort 1
public class Solution {
}

ListNode mid = findMedian(head); // O(n)

ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
ListNode middleDummy = new ListNode(0), middleTail = middleDummy;
} else if (head.val > mid.val) {
} else {
}
}

leftTail.next = null;
middleTail.next = null;
rightTail.next = null;

ListNode left = sortList(leftDummy.next);
ListNode right = sortList(rightDummy.next);

return concat(left, middleDummy.next, right);
}

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

private ListNode concat(ListNode left, ListNode middle, ListNode right) {
ListNode dummy = new ListNode(0), tail = dummy;

tail.next = left; tail = getTail(tail);
tail.next = middle; tail = getTail(tail);
tail.next = right; tail = getTail(tail);
return dummy.next;
}

return null;
}

}
}
}
``````

## convert sorted list to bst

``````
public class Solution {
if (head == null) {return null;}

ListNode last = slow;

while (fast.next != null && fast.next.next != null) {
last = slow;
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;
last.next = null;
TreeNode cur = new TreeNode(slow.val);
cur.right = sortedListToBST(fast);
return cur;
}
}
``````

## remove nth node from end of list

``````
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n <= 0) {
return null;
}

ListNode dummy = new ListNode(0);

ListNode preDelete = dummy;
for (int i = 0; i < n; i++) {
return null;
}
}
preDelete = preDelete.next;
}
preDelete.next = preDelete.next.next;
return dummy.next;
}
}
``````

``````
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) {
return null;
}

int carry = 0;
while(l1 != null && l2!=null){
int sum = carry + l1.val + l2.val;
point.next = new ListNode(sum % 10);
carry = sum / 10;
l1 = l1.next;
l2 = l2.next;
point = point.next;
}

while(l1 != null) {
int sum =  carry + l1.val;
point.next = new ListNode(sum % 10);
carry = sum /10;
l1 = l1.next;
point = point.next;
}

while(l2 != null) {
int sum =  carry + l2.val;
point.next = new ListNode(sum % 10);
carry = sum /10;
l2 = l2.next;
point = point.next;
}

if (carry != 0) {
point.next = new ListNode(carry);
}
}
}
``````

version1 : stack

``````

public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//require
ListNode ans=null;
Stack<ListNode> stack1=new Stack<ListNode>(),stack2=new Stack<ListNode>();
//invariant
while(l1!=null||l2!=null){
if(l1!=null){
stack1.push(l1);
l1=l1.next;
}
if(l2!=null){
stack2.push(l2);
l2=l2.next;
}
}
int a=0,b=0,carry=0,sum=0;
while(!stack1.isEmpty()||!stack2.isEmpty()){
if(!stack1.isEmpty())
a=stack1.pop().val;
else
a=0;
if(!stack2.isEmpty())
b=stack2.pop().val;
else
b=0;
sum=a+b+carry;
ListNode tmp=new ListNode(sum%10);
tmp.next=ans;
ans=tmp;
carry=sum/10;
}
if(carry!=0){
ListNode tmp=new ListNode(carry);
tmp.next=ans;
ans=tmp;
}

//ensure
return ans;
}
}
``````

version 2： reverse list 结合 add two numbers

## reverse nodes in k group

1、建立空的新链表list1. 2、如果原链表剩余元素个数不小于K个，则取K个元素，采用头插法构建反序的临时链表，插入list1的尾部。 3、如果链表剩余元素个数小于K个，则将剩余的链表插入到list1的尾部。

``````
private static ListNode reverse(ListNode pre, ListNode next){
ListNode last = pre.next;//where first will be doomed "last"
ListNode cur = last.next;
while(cur != next){
last.next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = last.next;
}
return last;
}

public static ListNode reverseKGroup(ListNode head, int k) {
if(head == null || k == 1)

ListNode dummy = new ListNode(0);
int count = 0;
ListNode pre = dummy;
while(cur != null){
count ++;
ListNode next = cur.next;
if(count == k){
pre = reverse(pre, next);
count = 0;
}
cur = next;
}
return dummy.next;
}
``````

## swap nodes in pairs

``````
public class Solution {

ListNode dummy = new ListNode(0);

n1.next = n2.next;
n2.next = n1;
// move to next pair
}
return dummy.next;
}
}
``````

h

### hexinyuan

Flaurel
2012/11/01
1K
1

kukudeku
2016/09/03
107
0

heiyexue
2014/09/09
0
0

SeaRise
2017/11/25
0
0

2016/02/27
77
0

2016/11/18
24
0

Real_man
03/21
0
0

1、ArrayList集合 ArrayList是List接口的一个实现类,它是程序中最常见的一种集合。在ArrayList内部封装了一个长度可变的数组对象,当存入的元素超过数组长度时,ArrayList会在内存分配一个更大...

03/08
0
0

1314Stone
2017/11/23
0
0

2016/06/20
30
0

jq如何拿到data-info的自定义属性 1.1 原生可以获取到所有属性el.attrbutes 1.2 jq的\$(el).attr('属性名称') 继承的几种方式，原型链 2.1 扩展原型对象实现继承 2.2 替换原型对象实现继承 2....

litCabbage
4分钟前
0
0
python语言规范

ghou-靠墙哭
8分钟前
0
0
istio 监控，遥测 （理论）

Istio提供了一种灵活的模型来强制执行授权策略并收集网格中服务的遥测。 基础架构后端旨在提供用于构建服务的支持功能。它们包括诸如访问控制系统，遥测捕获系统，配额执行系统，计费系统等之...

xiaomin0322
10分钟前
0
0

corejava hashcode相等的两个对象一定相等吗?equals呢?反过来相等吗? 介绍一下集合框架? hashtable,hashmap底层实现是什么?hashtable和concurrenthashmap底层实现的区别? hashmap和treemap的...

undefine
11分钟前
4
0
alpine安装软件指定安装源

linux-alpine安装软件指定安装源 一、永久修改apk下载源地址 vi etc/apk/repositories 替换成阿里源 http://mirrors.aliyun.com/alpine/v3.8/main/http://mirrors.aliyun.com/alpine/v3...

12分钟前
0
0
Centos7通过yum安装nginx

iplusx
14分钟前
0
0
ef .core Dapper Helper

using System; using System.Collections.Generic; using System.Configuration; using System.Data; using System.Data.SqlClient; using System.Threading.Tasks; using Dapper; using Dap......

Lytf
15分钟前
0
0
iOS 小笔记

1.以下代码打印什么     __block int val = 10;    void (^blk)(void) = ^{        printf("val=%d\n",val);        };       val = 2;    blk(); /...

17分钟前
0
0
【Spring Boot 系列 Spring Boot示例程序】

HansonReal
18分钟前
0
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意：判断数组中是否有重复元素 思路：构造一个set，不重复就加进去，重复返回true，如果数据量大的话，可以用布隆过滤器 Java实现： publ...

yysue
23分钟前
0
0