编程知识 cdmana.com

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

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

 

版权声明
本文为[/Shao Siming]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/11/20211109094540359a.html

Scroll to Top