[Java data structure] you must master the classic example of linked list interview (with super detailed illustration and code)

/Shao Siming 2021-11-25 17:57:32

Catalog

One , Write it at the front

Two , Classic examples of linked lists

1, Invert a single chain table

2, Given a node with a header head The non empty single chain table of , Returns the middle node of the linked list

3, Enter a linked list , Output the last number in the list k Nodes

4, Delete multiple duplicate values in the linked list

5, Palindrome structure of linked list

6, Merge two linked lists

7, Enter two linked lists , Find their first common node .

8, Judge whether a linked list has links

9, Find the first node of a ring with a linked list


One , Write it at the front

Linked list is almost the top priority of data structure , The linked list is also a necessary knowledge point for the interview of large factories , To learn the linked list well , The most important thing is to draw pictures to solve problems , If you think this blog is good , seek give the thumbs-up , For collection , Ask for comment , Your third company is the biggest driving force for my progress , I don't say much nonsense , Let's learn !!!

Two , Classic examples of linked lists

1, Invert a single chain table

 

public ListNode reverseList() {
if(this.head == null) {
return null;
}
ListNode cur = this.head;
ListNode prev = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}

 2, Given a node with a header head The non empty single chain table of , Returns the middle node of the linked list

public ListNode middleNode() {
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
if(fast == null) {
return slow;
}
slow = slow.next;
}
return slow;
}

 3, Enter a linked list , Output the last number in the list k Nodes

 public ListNode findKthToTail(int k) {
if(k <= 0 || head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k-1 != 0) {
fast = fast.next;
if(fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}

4, Delete multiple duplicate values in the linked list

// Delete all values as key The node of
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
// Final processing head
if(this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}

5, Palindrome structure of linked list

 public boolean chkPalindrome(ListNode A) {
// write code here
if(head == null) return true;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow Come to the middle -》 reverse
ListNode cur = slow.next;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// Reverse complete
while(head != slow) {
if(head.val != slow.val) {
return false;
}
if(head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}

6, Merge two linked lists

public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (headA != null && headB != null) {
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}

7, Enter two linked lists , Find their first common node .

 public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null
ps = headB;
int len = lenA-lenB;// Step two
if(len < 0) {
pl = headB;
ps = headA;
len = lenB-lenA;
}
//1、pl It always points to the longest linked list ps Always point to the shortest linked list 2、 I got the difference len Step
//pl Walk difference len Step
while (len != 0) {
pl = pl.next;
len--;
}
// Go at the same time Until we met
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}

8, Judge whether a linked list has links

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

 9, Find the first node of a ring with a linked list

 public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}

 

Please bring the original link to reprint ,thank
Similar articles

2021-11-25

2021-11-25

2021-11-25

2021-11-25