catalogue
82. Delete all nodes with duplicate numbers in the linked list
Sword finger offer22 Find the penultimate node in the lin k ed list
206. Reverse output the linked list
234. Judge whether the linked list is a palindrome linked list
21. Merge two ordered linked lists
141. Determine whether it is a ring linked list
142. Find the ring entry node of the ring linked list
160. Intersecting linked list, find intersecting nodes
83. Delete the duplicate elements in the ascending linked list so that each element appears only once
The first square node is the dummy head node defined by ourselves, which makes cur move backward from the head node. Prev and cur move together. When duplicate elements are encountered, prev points to the first non duplicate element
public class LeetCode83 {//There is a linked list arranged in ascending order. Give you the head node of the linked list,
// Please delete all duplicate elements so that each element appears only once.
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead=new ListNode(101);
dummyHead.next=head;
ListNode prev=dummyHead;
ListNode cur=prev.next;
while (cur!=null){
if(cur.val==prev.val){
prev.next=cur.next;
}else {
prev=prev.next;//Neither prev nor cur are duplicate elements
} cur=cur.next;//cur, go straight back
}return dummyHead.next;
}
}
82. Delete all nodes with duplicate numbers in the linked list
Similar to the previous question, three indexes are used here: prev, cur and next
public class LeetCode82 {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead=new ListNode(-1);
dummyHead.next=head;
ListNode prev=dummyHead;
ListNode cur=prev.next;
ListNode next=prev.next.next;
while (cur.next!=null ){
if (next.val==cur.val){
prev.next=next;
}else {
cur.next = next;
}next=next.next;
}return dummyHead.next;
}
}
Sword finger offer22 Find the penultimate node in the lin k ed list
Define a fast and low point to the head node. Fast starts from the beginning and takes k steps. It moves backward synchronously with fast and low. Fast and low are always separated by k units. When fast is empty, low is the penultimate node
public class LeetCodeOffer22 {//Find the penultimate node in the lin k ed list
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast=head;
ListNode low=head;
for (int i = 0; i < k; i++) {
fast=fast.next;
}
while (fast!=null){
fast=fast.next;
low=low.next;
}return low;
}
}876. Find the intermediate node of the linked list. If there are two intermediate nodes, the second one will be returned
Use the fast and slow pointers. The fast pointer takes two steps at a time and the slow pointer takes one step at a time. When the fast pointer is empty or its next node is empty, the slow pointer points to the intermediate node
public class LeetCode876 {
public ListNode middleNode(ListNode head) {
ListNode fast=head;
ListNode low=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
low=low.next;
}return low;
}
}
206. Reverse output the linked list
1. A new linked list is created by head interpolation, which is used when space complexity is not required
public class LeetCode206 {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null) {
return head;
}else {
ListNode dummyHead=new ListNode(5001);
while (head!=null){
ListNode node=new ListNode(head.val);
node.next=dummyHead.next;
dummyHead.next=node;
head=head.next;
}return dummyHead.next;
}}
2. Move in place and operate on the original linked list
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
else {
ListNode prev=null;
ListNode cur=head;
while (cur!=null){
ListNode next=cur.next;
cur.next=prev;
prev=cur;
cur=next;
}return prev;
}
}3. Recursion
public ListNode reverseList(ListNode head) {
if (head==null||head.next==null){
return head;
}else {
ListNode sec = head.next;
ListNode newHead = reverseList(head.next);
sec.next = head;
head.next = null;
return newHead;
}
}234. Judge whether the linked list is a palindrome linked list
For example, 1 -- > 2 -- > 2 -- > 1 is still 1 -- > 2 -- > 2 -- > 1 in reverse
First find the intermediate node, reverse output the linked list after the intermediate node (using the palindrome of the method in the previous question), and compare the new linked list with the first half of the linked list.
You can also palindrome the whole linked list, which will not be repeated here
public class LeetCode234 {
public boolean isPalindrome(ListNode head) {
ListNode middle=middleNode(head);
ListNode l2=reverseList(middle);
while (l2!=null){
if(l2.val!=head.val) {
return false;
}l2=l2.next;
head=head.next;
}return true;
} public ListNode middleNode(ListNode head) {//Intermediate node
ListNode fast=head;
ListNode low=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
low=low.next;
}return low;
}
public ListNode reverseList(ListNode head) {//Use recursion to output the linked list in reverse order (question 206)
if (head==null||head.next==null){
return head;
}else {
ListNode sec = head.next;
ListNode newHead = reverseList(head.next);
sec.next = head;
head.next = null;
return newHead;
}
}}21. Merge two ordered linked lists
Create a virtual head node and point to it last. Compare from the beginning node. The linked list with small value is connected behind the virtual head, and then compare the next value of the linked list with the head node of another linked list, and so on
public class LeetCode21 {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1==null){
return list2;
}
if (list2==null){
return list1;}
ListNode dummyHead=new ListNode(101);
ListNode last=dummyHead;
while (list1!=null && list2!=null){
if(list1.val<= list2.val){
last.next=list1;
last=list1;
list1=list1.next;
}else {
last.next=list2;
last=list2;
list2=list2.next;
}}
if(list1==null){//At this time, l1 or l2 is empty
last.next=list2;
}else {
last.next=list1;
}return dummyHead.next;
}
}141. Determine whether it is a ring linked list
Use the fast and slow pointers. When the fast and slow pointers meet, it is a circular linked list
public class LeetCode141 {
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode low=head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
low=low.next;
if (fast==low){
return true;
}
}return false;
}
}142. Find the ring entry node of the ring linked list
Use the speed pointer. Speed refers to fast and low starting from the beginning, two steps at a time, and one step at a time. According to the above question 141, if there is a ring, the two will meet at point b. at this time,
fast walking length: a+n(b+c)
low walking length: a+b
According to the fact that fast is twice as fast as low, we can deduce the formula: a=(n-1)(a+b)+c
At this time, low is at point b, so that third and low start moving at the same speed at the same time. According to the derived formula, they meet at the entrance of the ring
public class LeetCode142 {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode low=head;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
low=low.next;
if(low==fast){
ListNode third=head;
while (third!=low){
third=third.next;
low=low.next;
}return low;
}
}return null;
}
}160. Intersecting linked list, find intersecting nodes
The length of the intersecting part is c. let a and B start traversing at the same time. When one party reaches the end point, let it continue traversing from the header of the other party. A takes the route of a+c+b, and B takes the route of b+c+a. the two will meet at the intersection
public class LeetCode160 {//Intersecting linked list
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA=headA;
ListNode pB=headB;
while (pA!=pB){
pA=pA==null ? headB:pA.next;
pB=pB==null ? headA:pB.next;
}return pA;
}
}
Interview question 02.04 Split the linked list, put those less than x in front of X and those greater than x in the back
public class LeetCodeOffer0204 {//Split the linked list, put those less than x in front of X and those greater than x in the back
public ListNode partition(ListNode head, int x) {
if(head==null){
return null;
}
ListNode smallHead=new ListNode(101);
ListNode smallTail=smallHead;
ListNode bigHead=new ListNode(101);
ListNode bigTail=bigHead;
while (head!=null){//Traverse the original linked list
if (head.val<x){
smallTail.next=head;
smallTail=head;//Tail insert small chain table
}else {
bigTail.next=head;
bigTail=head;
}
head=head.next;
}
bigTail.next=null;//Splice two linked lists
bigTail.next=bigHead.next;
return smallHead.next;
}
}
There are so many questions related to the linked list. Pay attention!! We must draw more pictures to understand!!
Maybe the description is not in place or the code has any problems. Welcome to comment