数据结构与算法之美——链表——常见面试题分析

java哥 阅读:191 2021-06-15 11:20:03 评论:0

一、常见面试题如下

①单链表反转

②链表中环的检测

③两个有序的链表合并

④删除链表倒数第n个结点

⑤求链表的中间结点

二、单链表反转

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1、递归法实现

/** 
 * 单链表反转 
 */ 
public class LinkList { 
    private static class Node { 
        int data; 
        Node next; 
 
        public Node(int data) { 
            this.data = data; 
        } 
    } 
 
    /** 
     * 递归法是从最后一个Node开始,在谈栈的过程中将指针顺序置换 
     * 
     * @param head 
     * @return 
     */ 
    public static Node reverse(Node head) { 
        //递归终止条件是当前为空,或者下一个节点为空 
        if (head == null || head.next == null) { 
            return head; 
        } 
        //递归调用来反转每一个节点 
        Node cur = reverse(head.next); 
        //每一个节点是怎么反转的 
        head.next.next = head; 
        //防止循环链表,需要将head.next设置为空 
        head.next = null; 
        //每层递归都返回cur,也就是最后一个节点 
        return cur; 
    } 
 
    public static void main(String[] args) { 
        //1->2->3->4 
        Node node1 = new Node(1); 
        Node node2 = new Node(2); 
        Node node3 = new Node(3); 
        Node node4 = new Node(4); 
 
        node1.next = node2; 
        node2.next = node3; 
        node3.next = node4; 
 
        Node reverse = reverse(node1); 
        System.out.println(reverse.data); 
    } 
} 

       剑指offer中有一句话:栈的本质是递归。所以可以借助栈理解递归;先进后出,栈顶是递归终止条件,栈的每一层是递归的方法体

       递归的两个条件:

       ①终止条件是当前节点或者下一个结点为Null

       ②在函数内部,改变节点的指向,也就是head下一个节点指向head递归函数。

       代码分析:

       再对递归思想和代码进行深入的了解。

       1、首先找到递归的出口

       就是找到链表最后1个节点(尾节点),我们要反转当前的链表,就必须从尾节点开始,因为链表的性质就是:通过头节点来找到后面的节点进行操作,CRUD都需要从头节点开始找。找到当前链表的尾节点就是反转链表的头节点。

 if (head == null || head.next == null) { 
            return head; 
    }

  这个条件对应两种情况:

  当链表只有空节点时:

                   

  链表到尾节点时:

                          

   注意点:

   ①递归函数必须要有终止条件,否则会出错。

   ②递归函数先不断调用自身直到遇到终止条件后进行回溯,最终返回答案。

   递操作

   递就是拆分子问题。那么针对题中问题的拆分,如下:

                                                       

     那最后剩余这个节点怎么办呢?这个节点是尾节点,它反转只要让它指向前驱节点即可。

Node cur = reverse(head.next);

真正完成节点反转的是这句话。

                   head.next.next=head;

如果链表是 1 -> 2 -> 3 -> 4 -> 5,那么此时的cur就是5

而head是4,head的下一个是5,下下一个是空

       有1个小疑问就是head为啥是4?head作为头节点,一开始从尾节点反转时,应该是5,并且是怎么一步步来反转每一个节点呢?这就是递归解法的精髓了。 

                         

此时head确实是5,满足了出口条件。便返回到上一层,即有两个节点的情况。由于是递归调用,head就向前走了一步,此时head为4。

                       

        head.next.next = head。如下图所示:

        

        此时我们发现,链表有环了,这是不可以的,我们只要断开即可。

        

        当有两个节点时,单链表反转完成了。同理。归到第一次调用时完成单链表反转。

二、链表中环的检测

        有一个单链表,链表中有可能出现“环”,那么如何用程序来判断该链表是否为环链表呢?

         1、hash表   重复则有环

         2、快慢指针 龟兔赛跑(追及问题)

public class LinkListCycle { 
 
    public static boolean isCycle(Node head) { 
        //快慢指针,龟兔赛跑,追及问题 
        Node p1 = head;//慢指针 
        Node p2 = head;//快指针 
        while (p2 != null && p2.next != null) { 
            p1 = p1.next; 
            p2 = p2.next.next; 
            if (p1 == p2) { 
                return true; 
            } 
        } 
        return false; 
    } 
 
    public static boolean hasCycle(Node head) { 
        //借助set结构 
        Set<Node> nodesSeen = new HashSet<>(); 
        while (head != null) { 
            if (nodesSeen.contains(head)) { 
                return true; 
            } else { 
                nodesSeen.add(head); 
            } 
        } 
        return false; 
    } 
 
    private static class Node { 
        int data; 
        Node next; 
 
        Node(int data) { 
            this.data = data; 
        } 
    } 
 
    public static void main(String[] args) { 
        Node node1 = new Node(5); 
        Node node2 = new Node(3); 
        Node node3 = new Node(7); 
        Node node4 = new Node(2); 
        Node node5 = new Node(6); 
        node1.next = node2; 
        node2.next = node3; 
        node3.next = node4; 
        node4.next = node5; 
        node5.next = node2; 
        System.out.println(isCycle(node1)); 
        System.out.println(hasCycle(node1)); 
    } 
}

        hash法(hasCycle)本质是使用了HashSet作为额外的缓存。假设链表的节点数量为n,则该解法的时间复杂度是O(n)。由于使用了额外的存储空间,所以算法的空间复杂度同样是O(n)。 

        快慢指针(isCycle)相当于将问题转换为追及问题。假设链表的节点数量为n,则该算法的时间复杂度为O(n)。除两个指针外,没有使用额外的存储空间,所以空间复杂度是O(1)。


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号