# leetcode: 链表2

## 1. copy-list-with-random-pointer(拷贝一个带随机指针的链表)

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

```/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
if (head == null) return null;

//第一遍扫描：对每个结点进行复制，把复制出来的新结点插在原结点之后
while (node != null) {
RandomListNode newnode = new RandomListNode(node.label);
newnode.next = node.next;
node.next = newnode;
node = newnode.next;
}

//第二遍扫描：根据原结点的random，给新结点的random赋值
while (node != null) {
if (node.random != null) node.next.random = node.random.next;
node = node.next.next;
}

//第三遍扫描：把新结点从原链表中拆分出来
while (node != null) {
RandomListNode newnode = node.next;
node.next = newnode.next;
if (newnode.next != null) newnode.next = newnode.next.next;
node = node.next;
}

}
}
```

```# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
# @return a RandomListNode
if head == None: return None
while tmp:
newNode = RandomListNode(tmp.label)
newNode.next = tmp.next
tmp.next = newNode
tmp = tmp.next.next
while tmp:
if tmp.random:
tmp.next.random = tmp.random.next
tmp = tmp.next.next
while pnew.next:
pold.next = pnew.next
pold = pold.next
pnew.next = pold.next
pnew = pnew.next
pold.next = None
pnew.next = None

## 2. convert-sorted-list-to-binary-search-tree（有序链表转为二叉搜索树）

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

```  /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution {

public static TreeNode sortedListToBST(ListNode head) {
}

// 在区间[start, end)里递归，后面的end是包括在内的，这样可以避免要多用一个指针来记录mid前的节点
public static TreeNode rec(ListNode start, ListNode end){
if(start == end){
return null;
}

// 一次遍历找到中点的方法：快慢指针
ListNode mid = start;           // 该指针最终会指向中点
ListNode probe = start;         // 探针最终会到达end
while(probe!=end && probe.next!=end){       // 探针完成搜索，注意停止条件是和end比较而不是和null比！
mid = mid.next;
probe = probe.next.next;
}

TreeNode root = new TreeNode(mid.val);

root.left = rec(start, mid);
root.right = rec(mid.next, end);

return root;
}

}    /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution {

public static TreeNode sortedListToBST(ListNode head) {
}

// 在区间[start, end)里递归，后面的end是包括在内的，这样可以避免要多用一个指针来记录mid前的节点
public static TreeNode rec(ListNode start, ListNode end){
if(start == end){
return null;
}

// 一次遍历找到中点的方法：快慢指针
ListNode mid = start;           // 该指针最终会指向中点
ListNode probe = start;         // 探针最终会到达end
while(probe!=end && probe.next!=end){       // 探针完成搜索，注意停止条件是和end比较而不是和null比！
mid = mid.next;
probe = probe.next.next;
}

TreeNode root = new TreeNode(mid.val);

root.left = rec(start, mid);
root.right = rec(mid.next, end);

return root;
}

}  ```

View Code

```# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param head, a list node
# @return a tree node
def sortedArrayToBST(self, array):
length = len(array)
if length==0: return None
if length==1: return TreeNode(array[0])
root = TreeNode(array[length/2])
root.left = self.sortedArrayToBST(array[:length/2])
root.right = self.sortedArrayToBST(array[length/2+1:])
return root

array = []
while p:
array.append(p.val)
p = p.next
return self.sortedArrayToBST(array)```

## 3. merge two sorted lists  (合并两个排好序的链表)

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode p1 = l1;
ListNode p2 = l2;

while(p1 != null && p2 != null){
if(p1.val <= p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}

p = p.next;
}

if(p1 != null)
p.next = p1;
if(p2 != null)
p.next = p2;

}
}```

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param two ListNodes
# @return a ListNode
def mergeTwoLists(self, l1, l2):
if l1 == None:
return l2
if l2 == None:
return l1
dummy = ListNode(0)
tmp = dummy
while l1 and l2:
if l1.val <= l2.val:
tmp.next = l1
l1 = l1.next
tmp = tmp.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l2 == None:
tmp.next = l1
else:
tmp.next = l2
return dummy.next```

## 4.  sort list（链表排序）

Sort a linked list in O(n log n) time using constant space complexity.

```  /*
* 实现链表的合并排序：1、将链表划分成基本相等的两个链表
* 2、递归将这两个链接继续划分，直到链表的长度为0或者1为止
* 3、调用Merge（）将链接进行合并
*/```

```/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public static  ListNode sortList(ListNode head) {
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode list2 = slow.next;
slow.next = null;
list2 = sortList(list2);
}

private static ListNode merge(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
last.next = list1;
list1 = list1.next;
}else{
last.next = list2;
list2 = list2.next;
}
last = last.next;
}
if(list1 != null) last.next = list1;
else if(list2 != null) last.next = list2;
}
}```

View Code

这里涉及到一个链表常用的操作，即快慢指针的技巧。设置slow和fast指针，开始它们都指向表头，fast每次走两步，slow每次走一步，fast到链表尾部时，slow正好到中间，这样就将链表截为两段。

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a ListNode
dummy = ListNode(0)                             #归并时，新建一个链表头结点
p = dummy
p = p.next
else:
p = p.next
return dummy.next

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

## 5. reorder list(重排链表)

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.

```public class Solution {
int cnt = 0;
while (node != null) {
cnt++;
node = node.next;
}

if (cnt < 3) return;//3个以下的结点不需要移动

int k = (cnt - 1) / 2;//需要移动的后k个结点
int i = 1;
while (i++ < cnt - k) {
node = node.next;
}
ListNode begin = node.next;//用begin表示需要移动的后k个结点的开始
node.next = null;//把不需要移动的部分结尾设为null

//把需要移动的k个结点逆序
ListNode pre = begin;
ListNode cur = begin.next;
begin.next = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;

begin = cur;
pre = cur;
cur = next;
}

ListNode node2 = begin;
while (node1 != null && node2 != null) {
pre = node1;
cur = node2;

node1 = node1.next;//这两行一定要放在下面两行之前，因为pre和node1指向同一个结点，下面操作会改变node1的next；cur和node2同理
node2 = node2.next;

cur.next = pre.next;//这两行代码是把cur插入到pre后
pre.next = cur;
}
}
}  ```

View Code

2，将第二条链表L2翻转，如将L2={4,5}翻转为L2={5,4}。

3，按照题意归并链表。

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return nothing

# break linked list into two equal length
slow = fast = head                              #快慢指针技巧
while fast and fast.next:                       #需要熟练掌握
slow = slow.next                            #链表操作中常用
fast = fast.next.next
slow.next = None

while p:                                        #就完成了链表的翻转
tmp=p; p=p.next                             #运行时注意去掉中文注释
tmp.next=dummy.next
dummy.next=tmp

while p2:
tmp1 = p1.next; tmp2 = p2.next
p1.next = p2; p2.next = tmp1
p1 = tmp1; p2 = tmp2```

## 6 linked list cycle  i  (环判断)

Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

``` public boolean hasCycle(ListNode head) {
return false;
while(fast!=null && fast.next!=null)
{
if(slow==fast)
return true;
slow=slow.next;
fast=fast.next.next;
}
return false;
}```

View Code

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a boolean
return False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False```

## 7. linked list cycle ii (环的第一个节点)

Given a linked list, return the node where the cycle begins. If there is no cycle, return  `null` .

Can you solve it without using extra space?

x+ky+m = 2(x+ty+m)

=> ky = 2ty + x + m => (x + m) mod y = 0

``` 1 public ListNode detectCycle(ListNode head) {
3             return null;
6         while(true)
7         {
8             slow=slow.next;
9             if(fast==null || fast.next==null)
10                 return null;
11             fast=fast.next.next;
12             if(slow==fast)
13                 break;
14         }
16         while(slow!=fast)
17         {
18             slow=slow.next;
19             fast=fast.next;
20         }
21         return slow;
22     }```

View Code

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a list node
return None
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
break
if slow == fast:
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None```

## 8. remove-duplicates-from-sorted-list i (重复节点)

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given1->1->2, return1->2.
Given1->1->2->3->3, return1->2->3.

```public class Solution {

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

}
}```

View Code

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {

while(p != null){
if(p.val == prev.val){
prev.next = p.next;
p = p.next;
//no change prev
}else{
prev = p;
p = p.next;
}
}

}
}```

View Code

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a ListNode
while p.next:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next

View Code

## 9.remove-duplicates-from-sorted-list ii（重复节点）

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinctnumbers from the original list.

For example,
Given1->2->3->3->4->4->5, return1->2->5.
Given1->1->1->2->3, return2->3.

```public ListNode deleteDuplicates(ListNode head) {
ListNode t = new ListNode(0);

ListNode p = t;
while(p.next!=null&&p.next.next!=null){
if(p.next.val == p.next.next.val){
int dup = p.next.val;
while(p.next!=null&&p.next.val==dup){
p.next = p.next.next;
}
}else{
p=p.next;
}

}

return t.next;
}```

View Code

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a ListNode
dummy = ListNode(0); dummy.next = head
p = dummy
tmp = dummy.next
while p.next:
while tmp.next and tmp.next.val == p.next.val:
tmp = tmp.next
if tmp == p.next:
p = p.next
tmp = p.next
else:
p.next = tmp.next
return dummy.next```

原文作者：zxqstrong
原文地址: https://www.cnblogs.com/zxqstrong/p/5386393.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。