preface
The common skill of linked list exercises is to define pointers to replace head. If you go for head, it is either a mathematical problem. The circular linked list is solved by using mathematical ideas, or it is to define double pointers to operate the linked list.
1, Delete the node with the given value of key in the linked list
leetcode 203 questions
Define two variables, one is the node to be deleted, and the other is the precursor node of the node to be deleted. Finally, remember to judge whether the head node is the node to be deleted, and finally return to the head node.
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode cur=head.next;
ListNode prev=head;
while(cur!=null){
if(cur.val==val){
prev.next=cur.next;
}else{
prev=cur;
}
cur=cur.next;
}
if(head.val==val){
head=head.next;
}
return head;
}
2, Reverse linked list
Define the double pointer method, similar to the header insertion method, to insert the node header of the linked list
cur node is the node to be reversed, and curNext is the address value of the next node
1. First save the next address value of the node to be reversed, and then set the next of the header node to null
2. Only use the head insertion method to insert the node head.
leetcode 206
public ListNode reverseList(ListNode head) {
//Three pointer method to reverse the linked list
if(head==null||head.next==null){
return head;
}
ListNode cur=head;//Node to insert
ListNode curNext=head.next;//Save the address value of the next node
cur=curNext;
head.next=null;
while(cur!=null){
curNext=curNext.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}
3, Returns the intermediate node of the linked list
leetcode 876
Define the speed pointer, and pay attention to the even and odd nodes
Note that if the judgment condition is fast in the even case next. Next will cause null pointer exception. You must add both judgment conditions.
public ListNode middleNode(ListNode head) {
//Define fast and slow pointers. Fast pointers take one step more than slow pointers. Pay attention to odd and even numbers
if(head==null||head.next==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
4, Returns the penultimate node of the linked list
leetcode 19 questions
Define the fast and slow pointer. The fast pointer takes n-1 steps before the slow pointer. Modify the address value
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode dummy=new ListNode(0,head);
ListNode slow=dummy;
for(int i=1;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummy.next;
}
5, Split linked list
leetcode title link
Given the value of X, the front linked list is a value less than x, and the rear linked list is a value greater than or equal to X
There are many situations to consider
1. When inserting the linked list for the first time, both the head node and the tail node should point to the inserted node
2. Instead of the first insertion, just point the next value of the tail node to the inserted node, and then move the tail node back
3. If the previous linked list is empty, return the header of the following linked list
4. You also need to empty the next value of the following nodes, and then connect the two linked lists.
public ListNode partition(ListNode head, int x) {
//Split the linked list to divide those less than x into parts and those greater than or equal to x into parts! Good boy, yy
if(head==null){
return null;
}
ListNode xh=null;//Header node less than x
ListNode xe=null;;//Tail node less than x
ListNode Xh=null;//Header node greater than or equal to X
ListNode Xe=null;//Tail node greater than or equal to X
ListNode cur=head;
while(cur!=null){
if(cur.val<x){
//Less than X
if(xh==null){
//First insertion
xh=cur;
xe=cur;
}else{
//Not the first time
xe.next=cur;
xe=cur;
}
}else{
//>=Part of X
if(Xh==null){
//First insertion
Xh=cur;
Xe=cur;
}else{
//Not the first time
Xe.next=cur;
Xe=cur;
}
}
cur=cur.next;
}//Judge that all elements are greater than x. the previous linked list has no data to return to the subsequent linked list
if(xh==null){
return Xh;
}
xe.next=Xh;
if(Xh!=null){
//Set the last element to null
Xe.next=null;
}
return xh;
}
6, Merge two ordered linked lists
leetcode21 question
It is the same as merging ordered arrays. The linked list is more complex. You should save the following node addresses first, then define puppet nodes and connect them in the order of small values
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1. The idea is to set the puppet node first, put the linked list together, define two variables, save the following address, and then string it like a sugar gourd
ListNode dummy=new ListNode(-1);
ListNode head=dummy;//Save puppet node
ListNode cur1=l1;//Save the address value behind the node
ListNode cur2=l2;
while(l1!=null&&l2!=null){
cur1=l1.next;
cur2=l2.next;
if(l1.val<=l2.val){
dummy.next=l1;
l1=cur1;
}else{
dummy.next=l2;
l2=cur2;
}
dummy=dummy.next;
}
if(l1!=null){
dummy.next=l1;
}
if(l2!=null){
dummy.next=l2;
}
return head.next;
}
7, Delete duplicate nodes in ordered linked list
leetcode 83 questions
Double pointers will skip when they encounter equal. Finally, set the last node to null.
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(prev.val==cur.val){
cur=cur.next;
}else{
prev.next=cur;
prev=cur;
cur=cur.next;
}
}
prev.next=cur;
return head;
}
8, Circular linked list
leetcode 141 questions
First, use set to judge whether there is space, and the complexity is O (N), which does not meet the requirements of the topic
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set=new HashSet<>();
while(head!=null){
set.add(head);
head=head.next;
if(set.contains(head)){
return true;
}
}
return false;
}
2. The mathematical problem of fast and slow pointers. The fast pointer takes two steps and the slow pointer takes one step. If there is a ring, it will meet. If there is no ring, it will not meet. The spatial complexity is O(1)
public boolean hasCycle(ListNode head) {
//Speed pointer or mathematical problem
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(slow!=fast){
if(fast==null||fast.next==null){
return false;
}
fast=fast.next.next;
slow=slow.next;
}
return true;
}
9, Intersecting linked list
leetcode 160
1. First use the set storage node and then make cyclic judgment. The space complexity is O (N) and the time complexity is O (N), which is relatively slow
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode>set=new HashSet<>();
while(headA!=null){
set.add(headA);
headA=headA.next;
}
while(headB!=null){
if(set.contains(headB)){
return headB;
}
headB=headB.next;
}
return null;
}
2. Double pointers. I really didn't think of it. After reading the solution, I knew that the two linked lists were connected and whether there were nodes to be crossed
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur1=headA;
ListNode cur2=headB;
while(cur1!=cur2){
cur1=cur1==null?headB:cur1.next;
cur2=cur2==null?headA:cur2.next;
}
return cur1;
}
10, Add two numbers
leetcode 2 questions
There is no skill in this question, but pay attention to many special situations. After adding, judge the carry. I can execute it when I knock for the first time, but I can't pass it. I don't take into account the special circumstances.
Finally, the comment answer is to use a carry flag number to solve it. I learned.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode list=new ListNode(-1);
ListNode head=list;
int t=0;
while(l1!=null||l2!=null||t!=0){
if(l1!=null){
t+=l1.val;
l1=l1.next;
}
if(l2!=null){
t+=l2.val;
l2=l2.next;
}
list.next=new ListNode(t%10);
list=list.next;
t/=10;
}
return head.next;
}