Selected Likou, Niuke Chain surface test questions

2024-07-12

💎 欢迎各位大佬互三：my home page

1. Reverse a linked list

Thinking: If we don't open up additional space and only modify the original linked list, what method should we use?

Just start from the second element and insert the head one by one.

Then just modify the reference and point the last element to null


class Solution {
    public ListNode reverseList(ListNode head) {
        //head为null，直接返回
        if(head == null){
            return head;
        }
 
        ListNode cur = head.next;
        //head变为了末尾元素，指向null
        head.next = null;
        while(cur!=null){
            //curn为cur的next节点，便于往后移动
            ListNode curn = cur.next;    
            cur.next = head;
            head = cur;
            //更新cur
            cur = curn;
        }
        return head;
    }
}

2. The middle node of the linked list

876. Intermediate Node of Linked List

The first method that comes to mind for this problem is to define a cnt, traverse the linked list, then find the middle number, and then traverse the return value. This method is very simple. What if you want to find the middle node by traversing the linked list only once?

Here is a new idea: use the fast and slow pointers, start from the head, the fast pointer moves two nodes each time, and the slow pointer moves one node each time, so that the ultimate goal is achieved.

Next, let’s implement it:


class Solution {
    public ListNode middleNode(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;
        }
        return slow;
    }
}

Is this more efficient?

3. Return the kth last node

Interview Question 02.02. Return the kth last node

The first thing that comes to mind for this question is to traverse it once to get the total length, and then find the kth node from the end. However, with the foundation of the previous question, you can think of another method: Similarly,Using the fast and slow pointers, let fast go to k-1 nodes first, then slow and fast go at the same time. When fast's next is null, it means that fast has reached the last node, and slow is now at the kth last node.

This question indicates that the input k is legal, so no additional judgment is needed. What if k is illegal? And it is required that the length of the linked list cannot be directly calculated, so slow needs to judge while walking.


class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        int cnt = 0;
        while (cnt != k - 1) {
            //判断k的合法性，虽然本题不用判断
            fast = fast.next;
            if(fast == null){
                return;
            }
            cnt++;
        }
        //slow和fast同时移动
 
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

4. Merge linked lists

21. Merge two ordered linked lists

Ideas:Just define a new node newH, and then compare the val of headA and headB at once. In order to find the head node of the merged linked list, you also need to define a tmp = newH. Then tmp.next will point to the one with the smaller val.


class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode tmp = head;
    
        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;
        }else if(list2!=null){
            tmp.next = list2;
        }
        return head.next;
    }
}

5. Link list segmentation

CM11 Link List Split

This is an interview question on Niuke. The question is to split the linked list. The left side of x is smaller than x, and the right side is larger than x. The original order cannot be changed.

Idea: define a new node cur to traverse the original linked list (to prevent the original linked list from being changed), put all the numbers larger than x into one linked list, and all the numbers smaller than x into another linked list, and finally connect the two linked lists


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) {
                //处理刚开始为null的情况
                if (bs == null) {
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //都是比x大的情况
        if(bs == null){
            return as;
        }
        be.next = as;
        //最后都要置为null，不然可能会报错
        if(as!=null){
            ae.next = null;
        }
        return bs;
    }
}

It should be noted that if both are greater than x, that is, bs = null, then as is returned directly. Also, if as.next is set to null at the end

6. OR36 Palindrome structure of linked list

OR36 Palindrome structure of linked list

This is a question from Niuke. Because it has time complexity and space complexity requirements, it means that you cannot open an additional array, otherwise the space complexity will not be able to pass. Normal traversal is O(n) complexity.

The idea is this: first find the middle node slow of the linked list, then reverse the part from the middle to the end, traverse the head node backwards, traverse slow backwards, and compare them. If the values are different, it means it is not a palindrome structure.

We have already practiced reversing a linked list and finding the middle node.


public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        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开始到末尾反转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curn = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curn;
        }
        //判断回文
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            //判断偶数节点
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

It should be noted that there are also differences in the judgment of the linked list of odd nodes and the linked list of even nodes.

If an even-numbered node moves to the top, an infinite loop will occur. Therefore, additional judgment is required for even-numbered nodes.

7. Intersecting Linked Lists

160. Intersecting Linked Lists

The intersecting linked list is a transformation similar to "Y", as shown in the figure

The picture in the following question is also very clear

Idea: Because no matter A is shorter or B is shorter, their difference is the part before the intersection, we only need to move the long linked list by the difference, and then move the two linked list nodes backward at the same time, and their common node is the node to be intersected.


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        int cnta = 0,cntb = 0;
        //计算两个链表的长度
        while(pl!=null){
            pl = pl.next;
            cnta++;
        }
        while(ps!=null){
            ps = ps.next;
            cntb++;
        }
        //如果链表b长，就更新pl,ps
        int len = cnta - cntb;
        //上面求长度时pl,ps都为空了，所以这里再重新指向
        pl = headA;
        ps = headB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = cntb - cnta;
        }
        //移动差值
        while(len!=0){
            pl = pl.next;
            len--;
        }
        //找到相交节点
        while(pl!=ps){
            pl = pl.next;
            ps = ps.next;
        }
        //链表不相交的情况
        if(pl == null) return null;
        return pl;
    }
}

Finally, we need to add the non-intersecting case. Although we can pass this problem without adding it, we still need to add it for rigor.

8. Circular Linked List

8.1 Determine whether there is a loop

141. Circular Linked List

How to determine whether a linked list has a cycle:Or use the fast and slow pointers, just like two people running in the playground, one runs fast and the other runs slowly. Since the playground is a ring, the one who runs fast can definitely overtake the one who runs slowly in a circle, and then they will meet. But if it is not a ring, they will never meet, just like the goddess you can never catch up with no matter how hard you try.

But there is another situation. If it is a ring of two nodes, the fast pointer is defined to take 3 steps at a time, and the slow pointer takes 1 step at a time, then they will never meet.

Therefore, the number of steps that the defined pointers take each time also needs to be judged. If one takes 2 steps and the other takes 1 step, they will definitely meet.


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;
        }
        return false;
    }
}

8.2 Return to the node at the entrance of the loop

142. Circular Linked List II

This time, we need to determine whether it is a ring in the previous question and find the entry point into the ring. We can make the following inferences:


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){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

It is necessary to add that:

When the ring is very small, the final simplification result becomes the above, but the original code is still fine.

Technology Sharing