707. Design linked list
Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.
Implement these functions in the linked list class:
get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list.
addAtTail(val): append the node with value val to the last element of the linked list.
addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
Delete atindex (index): if the index is valid, delete the index node in the linked list.
Example:
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); // The linked list becomes 1 - > 2 - > 3
linkedList.get(1); // Return 2
linkedList.deleteAtIndex(1); // Now the linked list is 1 - > 3
linkedList.get(1); // Return 3
Tips:
All val values are within [1, 1000].
The number of operations will be within [1, 1000].
Do not use the built-in LinkedList library.
Source: LeetCode
Link: https://leetcode-cn.com/problems/design-linked-list
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Analysis & problem solving
analysis
I felt very simple when learning. I wrote down a lot of bug s myself..
Main problems:
1. How to define a node and what it contains
2. During the process of addition, deletion, query and modification, the change of size and the opening and closing of intervals
Two way linked list can be slightly modified on the basis of one-way linked list. This problem does not reflect the advantages of two-way linked list.
Problem solving (Java)
Single linked list:
//Single linked list
//First define the node with the pointer next and the content val
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
//Method of constructing linked list
class MyLinkedList {
//Define linked list length
int size;
//Define an empty header node
ListNode head;
public MyLinkedList() {
//Set initial value of linked list
size = 0;
head = new ListNode(0);
}
public int get(int index) {
//Define auxiliary nodes to traverse the linked list (because the head node is fixed and cannot be moved)
ListNode temp = head;
if (index >= 0 && index < size) {
//Traverse to find the node location of the index
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Returns the value of the location node
return temp.val;
} else {
return -1;
}
}
public void addAtHead(int val) {
//Create a new node with a value of val
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Note: first make the new node point to the next node of the head node, and then make the head node point to the new node
newNode.next = temp.next;
temp.next = newNode;
size++;
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Traverse to find the tail of the linked list
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
size++;
}
public void addAtIndex(int index, int val) {
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Because the node should also be placed when index=size, the right section is a closed section
if (index >= 0 && index <= size) {
//Traverse to find the position of the previous node of the index, because index=size should be considered
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Judge whether index=size
if (temp.next != null) {
newNode.next = temp.next;
}
temp.next = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
ListNode temp = head;
if (index >= 0 && index < size) {
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Method of deleting node
temp.next = temp.next.next;
size--;
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
Bidirectional linked list:
//Double linked list
//First define the node with the pointer next, pre and content val
public class ListNode {
int val;
ListNode next;
ListNode pre;
ListNode(int val) {
this.val = val;
}
}
//Method of constructing linked list
class MyLinkedList {
//Define linked list length
int size;
//Define an empty header node
ListNode head;
public MyLinkedList() {
//Set initial value of linked list
size = 0;
head = new ListNode(0);
}
public int get(int index) {
//Define auxiliary nodes to traverse the linked list (because the head node is fixed and cannot be moved)
ListNode temp = head;
if (index >= 0 && index < size) {
//Traverse to find the node location of the index
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Returns the value of the location node
return temp.val;
} else {
return -1;
}
}
public void addAtHead(int val) {
//Create a new node with a value of val
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Note: first make the new node point to the next node of the head node, and then make the head node point to the new node
if (temp.next != null){
temp.next.pre = newNode;
newNode.pre = temp;
}
newNode.next = temp.next;
temp.next = newNode;
size++;
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Traverse to find the tail of the linked list
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.pre = temp;
size++;
}
public void addAtIndex(int index, int val) {
ListNode newNode = new ListNode(val);
ListNode temp = head;
//Because the node should also be placed when index=size, the right section is a closed section
if (index >= 0 && index <= size) {
//Traverse to find the position of the previous node of the index, because index=size should be considered
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Judge whether index=size
if (temp.next != null) {
temp.next.pre = newNode;
newNode.next = temp.next;
}
temp.next = newNode;
newNode.pre = temp;
size++;
}
}
public void deleteAtIndex(int index) {
ListNode temp = head;
if (index >= 0 && index < size) {
//Note that this is not the same as the single linked list (it can also be the same), and self deletion is used here
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Delete node
if (temp.next != null){
temp.next.pre = temp.pre;
}
temp.pre.next = temp.next;
size--;
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/