算法篇04、链表相关算法-一一网

本篇主要讲解链表相关的算法；

前言 ListNode节点介绍

首先介绍一下我们本篇使用到的链表的节点类，本篇链表主要是解决leetcode上相关问题，因此节点没有使用泛型，直接使用的int；如果是定义数据结构，那么就需要使用泛型来保存节点的信息了；

四个构造方法，无参、一个参数、两个参数，还有一个把数组转换为链表的构造函数；重写的toString打印链表中的元素；

public class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode(int[] arr){
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("list: ");
        ListNode cur = this;
        while (cur!= null){
            builder.append(cur.val).append(" -> ");
            cur = cur.next;
        }
        builder.append("null");
        return builder.toString();
    }
}
复制代码

1、leetcode19–删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？
例如：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

此完全可以先扫描一遍链表，记录有多少个节点，然后倒数第n个节点就可以转化为正数多少个节点了，然后就可以再通过遍历找到待删除的节点删除即可；但此题进阶提示要我们只遍历一遍链表，这里我们就可以使用双指针技巧；

题解如下所示，我们首先定义虚拟头节点，让虚拟头节点的next指向head；然后我们定义快慢两个指针指向虚拟头节点，让快指针先前进n个节点，然后让快慢指针同时前进，当快指针到达链表尾时慢指针正好到达了待删除节点的前一个结点，此时就可以操作慢节点的next指向慢节点的next的next，这样就实现了遍历一遍链表就可以删除的操作；最后我们要注意返回dummyHead.next，而不要返回head，表面上看这两个表达的意思是一样的，但是有可能head被删除了，但我们其实并没有对head操作，因为head是个引用，还会指向原来的头节点；

//leetcode19 删除链表的倒数第 N 个结点
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode faster = dummyHead;
    ListNode slower = dummyHead;
    for (int i = 0; i < n + 1; i++) {
        faster = faster.next;
    }
    while (faster != null) {
        faster = faster.next;
        slower = slower.next;
    }
    slower.next = slower.next.next;
    return dummyHead.next;
}
复制代码

2、leetcode206–反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

例如：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

反转链表可以说是链表中比较经典的算法问题了，可以用两种方法解决，分别是迭代和递归；

迭代解法如下所示，定义pre代表当前节点的前一个结点，cur代表当前节点，next代表当前节点的下一个节点；然后让cur的下一个节点指向pre，pre指向cur，cur指向next，继续循环进行下一次反转，直到cur==null，也就是没有next了代表没有节点了，因为当前pre指向了cur，所以最后返回pre节点即可；

解法一迭代

//leetcode 206 反转链表 反转以head为头节点的链表，并返回反转后链表的头节点
public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        //真正发生发转的一步操作
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
复制代码

递归解法如下所示，首先定义递归终止条件，当前节点或者当前节点的下一个节点为null即返回；然后递归调用当前函数将head的next节点作为参数传入，并将返回值记录下来；接着调用head.next.next = head，这一步表示将当前节点的下一个节点的下一个节点指向自身，然后调用head.next = null，这一步表示将当前节点的下一个节点指向空，这两步执行完也就完成了反转；

解法二递归

//leetcode 206 反转链表
public ListNode reverseList(ListNode head) {
	//递归终止条件
    if (head == null || head.next == null) {
        return head;
    }

    //递归过程
    ListNode pHead = reverseList(head.next);
    //真正执行反转的两步操作
    head.next.next = head;
    head.next = null;
    return pHead;
}
复制代码

3、leetcode203–移除链表中元素

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

例如：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

迭代解法如下所示，首先创建虚拟头节点，让虚拟头节点的next指向head头节点，然后新建pre节点指向虚拟头节点，只要 pre.next != null 说明链表还有元素，此时只要pre.next.val = val 就说明pre的next节点就是待删除的节点，因此只需要 pre.next = pre.next.next 就可以把原pre的next节点删除了，否则直接让 pre = pre.next 继续进行下一个节点的判断；最后需要注意的就是返回dummyHead.next，不要返回head；

解法一迭代解法

//leetcode 203 移除链表中元素 迭代解法，使用虚拟头节点
public ListNode removeElements(ListNode head, int val) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode pre = dummyHead;
    while (pre.next != null) {
        if (pre.next.val == val) {
            pre.next = pre.next.next;
        } else {
            pre = pre.next;
        }
    }
    return dummyHead.next;
}
复制代码

解法二递归解法

递归解法如下所示，递归调用自身并将head.next作为参数传递进去，然后将返回值赋给head.next，递归回来之后如果 head.val = val ,说明当前head就是待删除的节点，让head指向head.next，并返回head；这就是整个递归过程；

//leetcode 203 移除链表中元素 递归
public ListNode removeElements(ListNode head, int val) {
	//递归终止条件
    if (head == null) {
        return null;
    }

    //递归过程
    head.next = removeElements(head.next, val);
    if (head.val == val) {
        head = head.next;
    }
    return head;
}
复制代码

4、leetcode24–两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
例如：
输入：head = [1,2,3,4]
输出：[2,1,4,3]

题解如下所示，首先定义递归终止条件，因为需要两个节点交换，所以当head或者head.next为空时显然应该停止递归了；

在递归过程中，首先保存一下当前head的next节点；然后递归调用，将next的next节点传入，也就相当于交换下一对节点了，然后把返回的节点赋值给head的next节点；最后将前面保存的next节点的next指向head，此时就完成了两两交换，最后返回next即可；

//leetcode24两两交换链表中的节点
public ListNode swapPairs(ListNode head) {
    //递归终止条件
    if (head == null || head.next == null) {
        return head;
    }

    //递归过程
    //暂存一下head的next节点
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
}
复制代码

5、数组转为链表

数组转为链表可以说是链表的常规操作，首先新建head头节点保存数组第一个元素，然后创建cur节点指向head，for循环遍历数组，将cur.next = new ListNode(arr[i])，并将 cur = cur.next 继续进行下一个元素的接入；

//数组转为链表
public ListNode convertArrayToListNode(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    ListNode head = new ListNode(arr[0]);
    ListNode cur = head;
    for (int i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return head;
}
复制代码

6、leetcode141–判断链表是否为环形链表

给定一个链表，判断链表中是否有环。如果链表中存在环，则返回 true 。否则，返回 false 。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则说明链表中存在环。

题解如下所示，本题是关于快慢双指针的典型应用，首先创建快慢两个节点都指向head节点，然后每次让快节点前进两位，让慢节点前进一位，如果快慢节点相撞，说明链表为环形链表，如果快节点到头了，说明不是环形链表；

//leetcode 141 判断链表是否为环形链表
//双指针中关于快慢双指针的典型应用
public boolean hasCycle(ListNode head) {
    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;
}
复制代码

7、leetcode142–返回环形链表的入环的起点

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

题解如下所示，本题是上一题的一个进阶版本，如果有环需要求出入环的第一个节点；创建一个布尔变量isCycle表示是否有环，如果有环置为true，如果有环，在相撞后，将快节点或者慢节点重新置为head，然后让快节点和慢节点以相同的速度一步一步的前进，此时当快慢节点相撞的位置就是入环的起点，此时返回快慢节点中的任意一个都可以；如果无环就返回null；

//leetcode 142 返回环形链表的入环的起点,如果不是环形链表返回null
public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    boolean isCycle = false;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            isCycle = true;
            break;
        }
    }
    slow = head;
    if (isCycle){
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }else {
        return null;
    }
}
复制代码

题目来源出处：

来源：力扣（LeetCode）
链接：leetcode-cn.com/problemset/…

文章版权归作者所有，未经允许请勿转载。

THE END

Android