【数据结构】——链表面试题详解

目录

一、  203. 移除链表元素 - 力扣（LeetCode）

二、206. 反转链表 - 力扣（LeetCode）

 三、876. 链表的中间结点 - 力扣（LeetCode）

​​​​​四、链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

五、21. 合并两个有序链表 - 力扣（LeetCode）

六、链表分割_牛客题霸_牛客网 (nowcoder.com) 

七、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

八、160. 相交链表 - 力扣（LeetCode） 

九、141. 环形链表 - 力扣（LeetCode） 

十、 142. 环形链表 II - 力扣（LeetCode）

---

一、  203. 移除链表元素 - 力扣（LeetCode）

 我们遍历一次链表来解决这个问题。首先我们定义两个节点，ListNode cur = head.next;

ListNode prve = head;在while（cur != null）{ } 循环里判断是否等于要删除的元素,当等于要删除的元素时:

  

当不等于要删除的元素时:

   

最后在单独判断一下头结点:

if(head.val == key){
     head = head.next;
}

完整代码展示:

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

二、206. 反转链表 - 力扣（LeetCode）

  

我们可以先定义一个head.next节点，然后再将头结点置为null：

ListNode cur = head.next;
head.next = null;

然后我们在循环里面需要记住cur.next，所以定义一个curNext = cur.next： 

  

然后我们运用头插法，将cur插入到head前面，再移动head和cur和curNext：
   

当然在一开始需要判断head和head.next是否为空，完整代码如下：

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

 三、876. 链表的中间结点 - 力扣（LeetCode）

 

 这个题在遍历一次链表的情况下，我们可以使用快慢指针：

即定义一个fast指针一次走两步，slow指针一次走一步，再遍历整个链表，当fast指针指向空时，slow指针便指向的是链表的中间位置。也会有两种情况，链表的长度为奇数和偶数时。

奇数时：

  

偶数时：

  

 完整代码：

public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

注：fast != null  && fast.next  != null 这两个的顺序不能调换,否则会空指针异常(先判断fast.next 是否为空时,fast已经是空了).

​​​​​四、链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

  

这道题我们还是运用了快慢指针的思想：

定义fast和slow指针，先让fast指针走k-1步，再两个指针一起走，直到fast.next为空。当然首先要判断k值是否合理,可以在fast指针走k-1步时实现；

代码如下：

public ListNode FindKthToTail(ListNode head, int k){
        if (head == null || k <= 0){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (k-1 != 0){
            fast = fast.next;
            if (fast == null){ //判断k是否合理
                return null;
            }
            k--;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

五、21. 合并两个有序链表 - 力扣（LeetCode）

   

 我们可以先实例化一个虚拟节点，然后在while(head1 != null && head2 != null){} 的时候,比较一下head1.val和head2.val的大小,将小的节点放到虚拟节点后面,,最后遍历完一个链表时,将剩下的链表整合到一起.  

完整代码:

public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(-1);//虚拟节点
        ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            } else {
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }

六、链表分割_牛客题霸_牛客网 (nowcoder.com) 

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针：

1.  这道题我们可以先分割再将它们串起来，先实例化两个结点 bs 和 as（before start，after start）
2. 遍历链表，将小于 x 的结点用尾插法插入到 bs 后，将大于 x 的结点用尾插法插入到 as后
3. 再实例化两个结点 be 和 ae（before end ，after end）作为两个结点的终点，再把 be 和 ae 串起来，返回 bs ，就得到了分割后的链表了

 

 下面我们来具体的实现代码：

public ListNode partition(ListNode head, int x) {
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;
            ListNode cur = head;
            while (cur != null){
                if(cur.val < x){
                    //插入到第一个段【尾插法】
                    if(bs == null){
                        //这是第一次插入元素
                        bs = cur;
                        be = cur;
                    }else{
                        be.next = cur;
                        be = be.next;
                    }
                }else {
                    //插入到第二个段【尾插法】
                    if (as == null) {
                        //这是第一次插入元素
                        as = cur;
                        ae = cur;
                    } else {
                        ae.next = cur;
                        ae = ae.next;
                    }
                }
                cur = cur.next;
            }
            //当没有小于x的结点时，bs就是null
            if(bs == null){
                return as;
            }
            //将be和as串起来
            be.next = as;
            //ae.next不一定null，需要手动将其置空
            if(as != null){
                ae.next = null;
            }
            return bs;
        }

七、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

 

这道题的思路如下： 

1. 首先通过快慢指针找到链表的中间位置
2. 然后从中间位置到末尾进行翻转链表（翻转单链表）
3. 最后一边从头一边从末尾开始遍历链表并且比较val值是否相等，知道相遇结束

 

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;
            }
            //逆置后半段的链表
            ListNode cur = slow.next;
            while (cur != null){
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //两头开始遍历比较val值是否相同
            while (head != slow){
                if (head.val != slow.val){
                    return false;
                }
                if (head.next == slow){//两边相遇了
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
    }

八、160. 相交链表 - 力扣（LeetCode） 

 思路：

1. 本题中两个链表相交是 Y 字形的，且相交的点的地址是相同。
2. 需要先求出两个链表的差值，因为两个链表的长度不一定相同，其相交之前的部分不一定相同，但是其相交的话相交之后的部分长度一定相同：
3. 让最长的链表走差值步
4. 然后再让两个链表一起走，相遇点就是相交的节点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //分别求出两个链表的长度
        int lenA = 0;
        int lenB = 0;
        ListNode p1 = headA;//代表永远指向长的链表
        ListNode p2 = headB;//代表永远指向短的链表
        while(p1 != null){
            lenA++;
            p1 = p1.next;
        }
        while (p2 != null){
            lenB++;
            p2 = p2.next;
        }
        p1 = headA;
        p2 = headB;
        //求出差值
        int len = lenA - lenB;
        if(len < 0){
            p1 = headB;//代表永远指向长的链表
            p2 = headA;//代表永远指向短的链表
            len = lenB - lenA;//len一定是一个正数
        }
        //让长的链表走了差值步
        while (len != 0){
            p1 = p1.next;
            len--;
        }
        //找到相同的点，直到相遇
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

九、141. 环形链表 - 力扣（LeetCode） 

思路：

1.  还是运用了快慢指针的思想，定义一个fast结点和一个slow结点。
2. slow走一步，fast走两步：因为如果链表带环，按照这样走的话，fast和slow最差的情况就是相差一圈，然后就会慢慢逼近。
3. 如果是slow走一步，fast走三步四步的情况下，slow和fast就会相遇的很慢，或者就会永远的错过。

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

十、 142. 环形链表 II - 力扣（LeetCode）

 

思路：

1.  这道题运用到了上一题的的找环的方法，然后还要找到环的入口。
2. 我们可以设起始点到入口点的距离为X，入口点到相遇点的距离为Y，环的长度为C，因为fast的速度是slow的两倍，所以距离也是两倍，fast的路程为：X + C + （C - Y），slow的路程为：X + C - Y，便可以联立等式：2（X + C - Y）= X + C + (C - Y),化简可以得到 X = Y,所以当slow和fast相遇之后，我们可以让slow = head，slow走X这段距离,fast刚好是走Y这段距离,因为距离相同,所以他们相遇的地方就是入口点:

public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
            ListNode fast = 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 fast;
    }