Doubly Linked List09
祁正阳
Doubly Linked List
Design Doubly Linked List
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
class MyLinkedList {
Node head;
int length;
class Node{
int val;
Node pre;
Node next;
Node(int val){
this.val=val;
}
}
/** Initialize your data structure here. */
public MyLinkedList() {
this.head=null;
this.length=0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index<0||index>=length) return -1;
int counter=0;
Node cur=head;
while(index!=counter){
cur=cur.next;
counter++;
}
return cur.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
Node cur= new Node(val);
Node temp=head;
if(this.length==0){
length++;
head=cur;
return;
}
cur.next=temp;
temp.pre=cur;
head=cur;
length++;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
Node cur= new Node(val);
if(this.length==0){
this.head=cur;
length++;
return;
}
Node curHead=head;
while (curHead.next!=null){
curHead=curHead.next;
}
curHead.next=cur;
cur.pre=curHead;
length++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if (index==0) {addAtHead(val);return;}
if (index==length){addAtTail(val);return;}
Node cur= new Node(val);
int counter=0;
Node currHead=head;
while (counter!=index){
counter++;
currHead=currHead.next;
}
cur.pre=currHead.pre;
cur.next=currHead;
currHead.pre.next=cur;
currHead.pre=cur;
length++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index<0||index>=length) return;
if (index==0) {
if(length==1){length--;head=null;return;}
head.next.pre=null;
head=head.next;
length--;return;
}
if (index==(length-1)){
Node temp=head;
while (temp.next!=null){
temp=temp.next;
}
temp.pre.next=null;
length--;return;
}
int counter=0;
Node currHead=head;
while (counter!=index){
counter++;
currHead=currHead.next;
}
currHead.pre.next=currHead.next;
currHead.next.pre=currHead.pre;
length--;
}
}
无尽的修改下成功了
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head=new ListNode(0);
ListNode temp=head;
while (l1!=null&&l2!=null){
if(l1.val>=l2.val){
temp.next=l2;
l2=l2.next;
}else {
temp.next=l1;
l1=l1.next;
}
temp=temp.next;
}
if(l1!=null) temp.next=l1;
if(l2!=null) temp.next=l2;
return head.next;
}
注意点：LinkedList不能自动扩容，尽量不要改变头节点
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
大佬思路：递归
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
ListNode head = new ListNode(0);
ListNode p = head;
int tmp = 0;
while(l1!=null || l2!=null || tmp!=0) {
if(l1!=null) {
tmp += l1.val;
l1 = l1.next;
}
if(l2!=null) {
tmp += l2.val;
l2 = l2.next;
}
p.next = new ListNode(tmp%10);
p = p.next;
tmp = tmp/10;
}
return head.next;
}
Flatten a Multilevel Doubly Linked List
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.
public Node flatten(Node head) {
if(head==null) return head;
Node curr = head;
while(curr!=null){
if(curr.child!=null){
Node down = curr.child;
while(down.next!=null) down = down.next;
Node temp = curr.next;
curr.next = curr.child;
curr.child.prev = curr;
curr.child= null;
down.next = temp;
if(temp!=null) temp.prev = down;
}
curr = curr.next;
}
return head;
}
## Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
深拷贝一个带随机指针的链表
```java
public Node copyRandomList(Node head) {
if(head==null) return null;
Node tempHead=head;
while(tempHead!=null){
Node temp = new Node(tempHead.val);
temp.next=tempHead.next;
tempHead.next=temp;
tempHead=tempHead.next.next;
}
tempHead=head;
while(tempHead!=null){
if(tempHead.random!=null)
tempHead.next.random=tempHead.random.next;
tempHead=tempHead.next.next;
}
tempHead=head;
Node newres=new Node(0);
Node res=newres;
while(tempHead!=null){
res.next=tempHead.next;
tempHead.next=tempHead.next.next;
tempHead=tempHead.next;
res=res.next;
// if(tempHead.next.next==null) break;
}
return newres.next;
}
思路：1.复制，2改变随机指针的方向，3抽离（3个遍历的用处）
public Node copyRandomList(Node head) {
if(head==null) return null;
Node tempHead=head;
while(tempHead!=null){
Node temp = new Node(tempHead.val);
temp.next=tempHead.next;
tempHead.next=temp;
tempHead=tempHead.next.next;
}
tempHead=head;
while(tempHead!=null){
if(tempHead.random!=null)
tempHead.next.random=tempHead.random.next;
tempHead=tempHead.next.next;
}
tempHead=head;
Node newres=new Node(0);
Node res=newres;
while(tempHead!=null){
res.next=tempHead.next;
tempHead.next=tempHead.next.next;
tempHead=tempHead.next;
res=res.next;
// if(tempHead.next.next==null) break;
}
return newres.next;
}
大佬思路：使用HashMap
Rotate List
Given the head of a linked list, rotate the list to the right by k places.
public ListNode rotateRight(ListNode head, int k) {
// ListNode tempHead = head;
// for (int i=0;i<k;i++) {
// while (tempHead.next != null) {
// tempHead = tempHead.next;
// }
// tempHead.next= head;
// ListNode temptemp=tempHead;
// while(temptemp.next!=tempHead){
// temptemp=temptemp.next;
// }
// temptemp.next=null;
// head=tempHead;
// }
// return tempHead;
// }
时间复杂度太高，
public ListNode rotateRight(ListNode head, int k) {
if(head==null) return head;
int len=1;
ListNode tail=head;
//calculate length
while(tail.next!=null){
tail=tail.next;
len++;
}
tail.next=head; //loop back to root
k%=len; //avoid unnecessary moves
for(int i=0;i<len-k;i++){
tail=tail.next;
}
ListNode NewHead=tail.next; //calculate new Head
tail.next=null;
return NewHead;
}
大佬思路：利用链表长度
类似资料：