linkedlist
linkedlist
hexinyuan 发表于4个月前
linkedlist
• 发表于 4个月前
• 阅读 0
• 收藏 0
• 评论 0

# 1. dummy node

• remove linked list elements
• remove duplicates from sorted list
• remove duplicates from sorted list ii (***)
• swap two nodes in linked list
• reverse 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
• reverse 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 (快慢指针，如果有环，快指针会追上慢指针，如果无环，快指针会走到空)
• linked list cycle ii （相遇后，slow指针回到原点，然后slow和fast各走一步，会在入口处相遇）

# 4. demo

• merge k sorted list
• panlindrome linked 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
• add two numbers
• add two numbers ii
• 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.断开返回复制出来的）

## remove linked list elements

``````
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode cur = head;//note:
ListNode pre = dummyHead;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
ListNode ret = dummyHead.next;
dummyHead = null;
return ret;
}
}
``````

## remove a node from sorted list

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

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

## 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 {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;

ListNode dummy = new ListNode(0);
dummy.next = head;
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) {
// Write your code here
ListNode dummy = new ListNode(-1);
dummy.next = head;
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;
}
}
``````

## reverse linked list

``````
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}

ListNode prev = null;
ListNode cur = head;

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

``````

## reverse linked list

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) {
return head;
}

ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;

for (int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}

ListNode premNode = head;
ListNode mNode = head.next;
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) {
if (head == null) {
return null;
}

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

while (head != null) {
if (head.val < x) {
left.next = head;
left = head;
} else {
right.next = head;
right = head;
}
head = head.next;
}

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

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

``````

## linked list cycle

``````
public class Solution {
public Boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}

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

## linked list cycle ii

>方法三（最简单）：

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

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

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

``````

public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next==null) {
return null;
}

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

while (head != slow.next) {
head = head.next;
slow = slow.next;
}
return head;
}
}

``````

## 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) {
heap.add(lists.get(i));
}
}

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode head = heap.poll();
tail.next = head;
tail = head;
if (head.next != null) {
heap.add(head.next);
}
}
return dummy.next;
}
}

``````

## panlindrome linked list

``````

public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}

ListNode middle = findMiddle(head);
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;
}

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

return slow;
}

private ListNode reverse(ListNode head) {
ListNode prev = null;

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

return prev;
}
}
``````

## odd even linked list

``````
public class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while(odd.next != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
``````

## reorder list

``````
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
//1.找到中点
ListNode middle = findMiddle(head);
//2.反转后半部分
middle.next = reverse(middle);
//3.合并两个部分
ListNode left = head;
ListNode right = middle.next;
head = merge(left, right, middle);
System.out.println(head);
}

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;
}
}

``````
``````
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
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
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;
}
}
``````

## rotate list

``````
public class Solution {
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length ++;
head = head.next;
}
return length;
}

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

int length = getLength(head);
n = n % length;

ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;

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

while (head.next != null) {
tail = tail.next;
head = head.next;
}

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

## insertion sort list (****)

``````

public class Solution {
public ListNode  insertionSortList(ListNode head) {
ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode cur = head;
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;
ListNode  cur = head;
while (cur != null && cur.val <= x){
pre = cur;
cur = cur.next;
}
return pre;
}
}

``````

## sort list

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

private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
if (head1 != null) {
tail.next = head1;
} else {
tail.next = head2;
}

return dummy.next;
}

public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode mid = findMiddle(head);

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

return merge(left, right);
}
}

// version 2: Quick Sort 1
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

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;
while (head != null) {
if (head.val < mid.val) {
leftTail.next = head;
leftTail = head;
} else if (head.val > mid.val) {
rightTail.next = head;
rightTail = head;
} else {
middleTail.next = head;
middleTail = head;
}
head = head.next;
}

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);
}

private ListNode findMedian(ListNode head) {
ListNode slow = head, fast = head.next;
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;
}

private ListNode getTail(ListNode head) {
if (head == null) {
return null;
}

while (head.next != null) {
head = head.next;
}
return head;
}
}
``````

## convert sorted list to bst

``````
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {return null;}
if (head.next == null) {return new TreeNode(head.val);}

ListNode slow = head;
ListNode fast = head;
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);
if (head != slow) cur.left = sortedListToBST(head);
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);
dummy.next = head;

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

## add two numbers

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

ListNode head = new ListNode(0);
ListNode point = head;
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);
}
return head.next;
}
}
``````

## add two numbers ii

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)
return head;

ListNode dummy = new ListNode(0);
dummy.next = head;
int count = 0;
ListNode pre = dummy;
ListNode cur = head;
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 {

public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;

head = dummy;
while (head.next != null && head.next.next != null) {
ListNode n1 = head.next, n2 = head.next.next;
// head->n1->n2->...
// => head->n2->n1->...
head.next = n2;
n1.next = n2.next;
n2.next = n1;
// move to next pair
head = n1;
}
return dummy.next;
}
}
``````

×