当前位置：网站首页>List interview common questions

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head= head.next;
        }
        return head;
    }
}

2. Reverse a linked list

link 206. Reverse a linked list - Power button （LeetCode）

Subject requirements

Look at the

Code up

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;// The chain list is empty 
        if(head.next == null) return head;// Note that there is only one node 

        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext= cur.next; 
            cur.next = head;
            head =cur;
            cur = curNext;
        }
    return head;
    }
}

3. The middle node of a list

link 876. The middle node of a list - Power button （LeetCode）

Subject requirements

Look at the

Code up

4. Last in the list k Nodes

link Last in the list k Nodes _ Niuke Tiba _ Cattle from (nowcoder.com)

Subject requirements

Look at the

Code up

5. Merge two ordered lists

link 21. Merge two ordered lists - Power button （LeetCode）

Subject requirements

Look at the

Code up

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(-1);// Puppet node   Virtual node 
        ListNode tmp = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            } else {
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }
    if(list1 != null) {
        tmp.next = list1;
    }
    if(list2 != null) {
        tmp.next = list2;
    }
    return newHead.next;
    }
}

6. Link list segmentation

link Link list segmentation _ Niuke Tiba _ Cattle from (nowcoder.com)

Subject requirements

Look at the

Code up

import java.util.*;

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;
        ListNode be = null;
        
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                // Insert into the first paragraph 
                if(bs == null) {
                    // This is the first time to insert an element 
                    bs = cur;
                    be = cur;
                }else {
                    be.next =cur;
                    be = be.next;
                }
            } else {
                // Insert into the second paragraph 
                if(as == null) {
                    as =cur;
                    ae =cur;
                }else {
                    ae.next =cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs == null) {
            return as;
        }
        be.next =as; 
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
}

7. Palindrome structure of linked list

link Palindrome structure of linked list _ Niuke Tiba _ Cattle from (nowcoder.com)

Subject requirements

Look at the

Code up

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if(A == null || A.next == null) {
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        // Find the midpoint 
        while(fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // Flip 
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // contrast 
        while(A != slow) {
            if(A.val != slow.val) {
                return false;
            }
            // Even number case 
            if(A.next != slow) { 
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

8. Intersecting list

link 160. Intersecting list - Power button （LeetCode）

Subject requirements

Look at the

Code up

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1. Find the length of two linked lists 
        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;//pl It means to point to the long linked list forever 
        ListNode ps = headB;//ps Stands for always pointing to a short linked list 
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //2, Find the difference length of two linked lists  len It must be a positive number 
        int len = lenA -lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //3. Let the long linked list take the difference length first 
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //4. Let's go again , meet 
        while(pl != ps && pl != null) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null) {
            return null;
        }
        return pl;
    }
}

9. Circular list

link 141. Circular list - Power button （LeetCode）

Subject requirements

Look at the

First , Understand what is a linked list with links ,
By a node in the linked list , Keep looking for next The pointer , It must reach this node again , Such a list is said to have rings , And each node of the linked list with a ring next The pointer , Not for null.

secondly , If you continue to consider using the speed pointer to do this problem , So fast pointer fast Take a few steps at a time ,

（1） If the pointer is fast fast Two steps each time , Slow pointer slow One step at a time , We must meet

（2） If the pointer is fast fast Every time I go 3 Step , go 4 Step ... go n Step , May not meet

So as long as the pointer is fast fast Every time I go 2 Step , The slow pointer goes every time 1 Step , You can definitely catch up , This problem is based on this idea

Code up

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

10. Circular list II

link 142. Circular list II - Power button （LeetCode）

Subject requirements

Look at the

Code up

public class Solution {
    public ListNode detectCycle(ListNode head) {
        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;
        }
        slow = head;
        while(slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

原网站

版权声明
本文为[Come to the pot]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/188/202207062049065479.html