10道经典链表面试题

目录

1.删除链表中等于给定值val的所有节点

2.反转一个单链表

3.给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则    返回第二个中间结点

4.输入一个链表，输出该链表中倒数第k个结点

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所     有节点组成的

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的        结点之前

7. 链表的回文结构

8. 输入两个链表，找出它们的第一个公共结点

9. 给定一个链表，判断链表中是否有环

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

1.删除链表中等于给定值val的所有节点

迭代：

    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return null;

        //处理头
        while(head != null && head.val == val) {
            head = head.next;
        }

        //处理中间和尾巴
        ListNode cur = head;
        if(cur != null) {
            while(cur.next != null) {
                if(cur.next.val == val) {
                    cur.next = cur.next.next;
                } else {
                    cur = cur.next;
                }
            }
        }
        return head;
    }

1.处理头：写在前面就要写成循环，因为前两个或前面有 >=2 个待删除的元素时，一个if条件语句     是解决不了的，而且条件必须包含head不为空，因为在删除的过程中，head一直在往后走，防     止出现空指针异常如果要用 if，则需要写在后面。

2.处理中间为尾巴：看下图

递归：

    public ListNode removeElements(ListNode head, int val) {
        if (head == null)
            return head;
        //先递归到最后一个结点，然后用上一次递归的head的next域接收
        head.next = removeElements(head.next, val);
        //如果此时的head的val是要删除的元素，即返回它的next
        return head.val == val ? head.next : head;
    }

注释看不明白的话，下图作为辅助理解： 

 2.反转一个单链表

    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        //处理一个结点的情况
        if(head.next == null) return head;

        ListNode pre = null;
        while(head != null) {
            ListNode headNext = head.next;
            head.next = pre;
            pre = head;
            head = headNext;
        }
        return pre;
    }

思路：

做这个题的时候，我们需要两个额外的"指针"，一个用来保存 head 的地址，一个用来保存head.next 的地址，因为每次都需要把自己的next域改为前一个结点的地址，然后不断往后走，直到 head 为空，，，

 图解：

3.给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

    public ListNode middleNode(ListNode head) {
        if(head == null) return null;
        //if(head.next == null) return head;
        ListNode fast = head;//一次走两步
        ListNode slow = head;//一次走一步
        //循环条件是把两种情况 && 在了一起
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

 解题中需要注意的点：

1.我们定义快慢指针，最初都指向head，然后一个走一步，一个走两步---》路程相同，fast       的速度是slow的两倍，当，fast到终点的时候，slow一定在路程的中间；

2.我们需要分情况讨论，分别是：奇数个结点和偶数个结点两种情况；

3.两种情况让循环终止的条件必须 && 在一起，根据短路原理，因为只可能存在两种情况中        的一种，而我们又不知道具体是哪一种情况，所以一个条件不满足，就要让循环终止。

图解：

4.输入一个链表，输出该链表中倒数第k个结点

    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null) {
            return null;
        }
        //判断 k 的合法性
        if(k <= 0) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;
        //先让 fast 走 k-1 步
        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;
    }

这个题和找链表的中间结点异曲同工，主要注意的点就是返回倒数第 K 个结点的时候，此时的 fast 与 slow 之间相差 K - 1 步，所以我们的思路就是先让 fast 走 K - 1 步，然后再一起走，直到fast走到最后一个结点，，，

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null && list2 == null) return null;
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        //我创建一个新的空结点，两链表互相从头开始比较，把较小的接在新的结点后面
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        //有一个为空就退出循环
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //循环走到这里，一定有一个链表为空
        cur.next = list1 == null ? list2 : list1;
        return newHead.next;
    }

 思路：

1.我们 new 一个空结点，作为新的链表的头，然后循环不断比较两个链表的值，把较小的一     个接在新的头后面，直到其中一个链表为空，就退出循环，，，

2.退出循环时，一定有一个链表为空，此时就把不为空的链表接在新链表尾结点的 next 域；

图解：

 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

    public ListNode partition(ListNode pHead, int x) {
        //申请两个头和尾，小于x的放bs,be，其余的放在as,ae;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                }
            } else {
                if(as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        //如果小的数据这一边为空，直接返回大的数据这一边的头
        if(bs == null) {
            return as;
        }
        
        be.next = as;
        if(ae != null && ae.next != null) {
            ae.next = null;
        }
        return bs;
    }

思路：

我们申请两个独立的链表，并都赋予头和尾，把小于x值的全部放在一个链表中，大于x的值全部放在一个链表中，如果都不为空，就把小的链表的尾的next指向大的链表的头，如果小的链表为空，需要单独处理，再一个要注意的点是：大的链表的尾巴可能不为空，所以我们要将其置为空。

图解： 

7. 链表的回文结构

public boolean chkPalindrome(ListNode A) {
        if(A == null) {
            return false;
        }
        //只有一个结点也是回文结构
        if(A.next == null) {
            return true;
        }
        //1.先走到中间结点。2.再反转右边的
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //一个从头走，一个从尾走
        while(A != slow) {
            if(A.val != slow.val) {
                return false;
            } 
            if(A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }

思路：

1.我们用快慢指针，找到链表的中间结点

2.把中间结点的右半部分反转

3.反转后的 slow 此时指向链表尾结点，然后让头节点 A 和尾结点 slow 同时一步一步走

4.考虑奇数和偶数两种情况，奇数情况两结点一定会相遇，偶数结点，两结点不会相遇，但     是会出现在两个中间结点，所以要加上 if 条件判断一下，否则 slow 又往回走了，，，

图解： 

8. 输入两个链表，找出它们的第一个公共结点

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;

        int lenA = 0;
        int lenB = 0;
        ListNode fast = headA;//指向较长的链表
        ListNode slow = headB;//指向较短的链表

        //分别求两链表的长度
        while(fast != null) {
            lenA++;
            fast = fast.next;
        }
        while(slow != null) {
            lenB++;
            slow = slow.next;
        }
        //重新指回头节点
        fast = headA;
        slow = headB;

        //如果 len < 0 就把 fast 改为指向长的链表
        int len = lenA-lenB;
        if(len < 0) {
            fast = headB;
            slow = headA;
            len = lenB-lenA;
        }
        //先让长的链表走差值步
        while(len != 0) {
            fast = fast.next;
            len--;
        }
        //if(fast == null) return null;
        //长链表走完差值步，再和短链表一起走
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

思路：

考虑两链表的长度，长度相同就不用处理，主要是长度不相同的情况，我们首先要分别计算两链表的长度，然后让长的链表先走差值步，然后再一起走，相遇的时候，返回即可。

图解：

9. 给定一个链表，判断链表中是否有环

    public static boolean hasCycle(ListNode head) {
        //空和一个结点都不成环
        if(head == null || head.next == null) return false;
        //两结点初始指向不能相同，否则循环进不去
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while(fast != slow) {
            //快指针走动的过程中，考虑没有环的情况
            if(fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

思路：快慢指针

既然一个指针走一步，一个指针走两步能实现，那一个指针走一步，一个指针走三步，走四步，不是可以更块相遇吗？？能否实现？？

答案肯定是不能这样做的，因为两倍速的走，每次都是以一步的距离进行追击，如果三倍速，四倍速的走，巧合的情况下确实可以提高效率，就怕它不巧合，出意外，导致永远都不能相遇；

 比如这个图：假设 fast 指向1位置，slow 指向2位置，fast 以slow三倍速的走，就永远不会相遇，这里的相遇和生活中的 跑操场追赶 不一样，这里是走的过程中不判断，停下来才判断两指针的指向是否一样。

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while(fast != slow) {
            if(fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        //让其中一个指针从头开始走，一个指针从相遇点开始走
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

这道题需要推导出一个公式：看完图解基本上就能懂了：

不管是大环还是小环，其实我们只要推导出 X = Y 这个公式，让其中一个指针指向 head，另一个指针指向相遇点，两者以相同的速度走，大环的情况，两个指针走的路程分别是 X,Y, 最后在入环点相遇；小环情况，两个指针走的路程分别为 X, (N-1)C, 也就是说，从相遇点开始走的那个指针在小环里面转了很多圈之后，最后走个 Y 的距离就与另一指针相遇了。

谢谢观看！！