链表经典练习题合集（Java版）_java链表算法题

 最近开始了数据结构的学习，数据结构是比较抽象的，需要不断的进行画图总结，不断地刷相关的题来加强自己对于数据结构的理解，我会不断地更新博客以及上传自己的做题记录以及题解，希望可以给大家带来帮助，也希望大家可以指出我存在的问题，共同进步☺

这是我的gitee链接，所有的代码都已上传至gitee中：gitee代码仓库

目录

移除链表元素 

反转链表 

链表的中间结点 

链表中倒数第k个结点 

合并两个有序链表

 

---

移除链表元素 

原题链接：203.移除链表元素

题目描述：

给你一个链表的头结点head和一个整数val，请你删除链表中所有满足Node.val == val的结点，并返回新的头结点.

例如：

输入：head = [1,2,6,3,6], val = 6

返回：[1,2,3] 

以上述输入为例，则此时链表的存储可抽象为如下所示

解决思路

遍历一次链表，实现删除所有的val值，定义两个引用prev和cur，使prev = head，cur = head.next,如图所示：

接下来判断cur.val是否等于所要删除的值，如果不相等，则令prev = prev.next ，cur = cur.next.

如果相等，则令cur = cur.next，prev.next = cur，即可完成删除操作

最后再判断一下头结点的val值是否与val值相等，如果相等则返回head.next，否则返回head.

具体代码如下：

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

反转链表 

 原题链接：206.反转链表

题目描述：

给你一个单链表的头结点head，请你反转链表，并返回反转后的链表

例如：

输入：head = [1,2,6,3,5]

输出：[5,3,6,2,1] 

 以上述输入为例，则此时链表的存储可抽象为如下所示

解决思路 

利用头插法的思想，完成对于单链表逆置操作.

首先令cur = head，保存链表，然后再将head置为null，之后依次遍历cur，将其以头插法的方式插入head即可.

上述图片为第一次头插后各个引用的状态，之后继续以这种方式进行头茬，直至cur == null，此时单链表已完成逆转.

具体代码实现 

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

链表的中间结点 

 原题链接：876.链表的中间结点

题目描述：

给定一个头结点为head的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个。

例如：

输入：[1,2,3,4,5]

输出：此列表中的结点3（序列化形式[3,4,5]） 

解题思路 

思路1：

首先遍历一遍单链表，求出单链表的长度length，将得到的长度除以2得到step，再从该链表的头结点开始走step步，即可得到中间结点.

代码如下：

    public ListNode middleNode(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while(cur != null) {
            length++;
            cur = cur.next;
        }
        int step = length / 2;
        for(int i = step; i > 0; i--) {
            head = head.next;
        }
        return head;
    }

 思路2（快慢指针思想）：

一种更先进的算法，只需遍历一遍链表即可得到中间结点.

利用快慢指针的思想，快指针每次走两步，慢指针每次走一步，当快指针指向null时，慢指针刚好在中间结点的位置.

其中红色剪头表示第一次走，绿色剪头表示第二次，当fast.next == null或者fast == null时，循环结束，此时慢指针所处的位置就是中间结点的位置.

具体代码实现 

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

链表中倒数第k个结点 

 原题链接：链表中倒数第k个结点

题目描述：

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

例如：

输入：1, {1,2,3,4,5}

输出：{5} 

思路1：

首先遍历一遍链表，求出链表的长度length，再利用length减去k得到实际需要走几步就可以得到倒数第k个结点

具体代码如下：

    public ListNode FindKthToTail(ListNode head,int k) {
        int length = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            length++;
        }
        // 一定要记得判断k是否合法
        if(length < k) {
            return null;
        }
        int step = length - k;
        for(int i = step; i > 0; i--) {
            head = head.next;
        }
        return head;
    }

思路2（快慢指针思想）： 

该题使用快慢指针思想，只需遍历一次链表只可得到结果，首先快指针先走k-1步，然后快指针和慢指针一起走，当fast.next == null时，此时slow指向的位置即为倒数第k个结点.

例如要求出下图倒数第三个结点，首先fast先走两步

之后快慢指针一起走

具体代码实现

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

合并两个有序链表

 原题链接：21.合并两个有序链表

题目描述：

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

例如：

输入：l1 = [1,2,4]     l2 = [1,3,4]

输出：[1,1,2,3,4,4] 

解题思路

建立一个新的结点newList，依次比较list1和list2每个结点的值的大小，将小的那个结点以尾插法插入newList中，最终就可以得到新的有序的链表.

具体代码实现

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newList = new ListNode();
        ListNode tmp = newList;
        while(list1 != null && list2 != null) {
            if(list1.val > list2.val) {
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            } else {
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }
        }
        if(list1 == null) {
            tmp.next = list2;
        } else {
            tmp.next = list1;
        }
        return newList.next; 
    }