链表

今天主要是把链表专题刷完了，链表专题的题目不是很难，基本都是考察对链表的操作的理解。

在处理链表问题的时候，我们通常会引入一个哨兵节点（dummy），dummy节点指向原链表的头结点。这样，当我们对头结点进行操作的时候就可以直接使用dummy节点，不用进行特判。

在对链表进行操作的时候 while的循环条件也是容易犯错的地方，我们不应该死记这题该是cur != null还是cur.next != null又或是其他。而是应该画个图，手动模拟一下，便知道结束的条件。

203.移除链表元素

题意：删除链表中等于给定值 val 的所有节点。

示例 1：

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

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

示例 2：

输入：head = [], val = 1

输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7

输出：[]

思路

遍历列表找到要删除的节点的前一个节点，修改该节点的指针跳过要删除的节点。

关键在于，处理头结点和如何找到要删除的前一个节点。我们可以使用一个哨兵节点和pre指针来实现。

pre初始值为哨兵节点，cur初始值是头结点。这样每次pre和cur都向后移一位即可,判断如果cur等于要删除的节点就让pre = cur.next，循环的条件为cur != null。

代码

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        ListNode dummy = new ListNode();

        dummy.next = head;

        ListNode pre = dummy;

        ListNode cur = head;

        while (cur != null) {

            if (cur.val == val) {

                pre.next = cur.next;

            } else {

                pre = cur;

            }

            cur = cur.next;

        }

        return dummy.next;

    }

}

707.设计链表

题意：

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

思路

本题不是一道算法题，是一道考察对链表的功能的具体实现的设计题。

熟悉链表具体操作即可，同样的我们引入哨兵节点和一个存储链表大小的size变量会方便我们的操作。

代码

class ListNode {

    int val;

    ListNode next;

    ListNode(){}

    ListNode(int val) {

        this.val = val;

    }

}

class MyLinkedList {

    int size; // 链表长度

    ListNode head; // 虚拟头结点

    public MyLinkedList() {

        size = 0;

        head = new ListNode(0);

    }

    public int get(int index) {

        if (index < 0 || index >= size) return -1;

        ListNode cur = head;

        // 包含一个虚拟头结点，所以要<=

        for (int i = 0; i <= index; i ++ ) {

            cur = cur.next;

        }

        return cur.val;

    }

    public void addAtHead(int val) {

        addAtIndex(0, val);

    }

    public void addAtTail(int val) {

        addAtIndex(size, val);

    }

    public void addAtIndex(int index, int val) {

        if (index > size) return;

        if (index < 0) index = 0;

        size ++;

        ListNode pre = head;

        // 包含一个虚拟头结点，所以要<=

        for (int i = 0; i < index; i ++ ) {

            pre = pre.next;

        }

        ListNode toAdd = new ListNode(val);

        toAdd.next = pre.next;

        pre.next = toAdd;

    }

    public void deleteAtIndex(int index) {

        if (index < 0 || index >= size) return ;

        size --;

        if (index == 0) {

            head = head.next;

            return ;

        }

        ListNode pre = head;

        for (int i = 0; i < index; i ++ ) {

            pre = pre.next;

        }

        pre.next = pre.next.next;

    }

}

/**

 * Your MyLinkedList object will be instantiated and called as such:

 * MyLinkedList obj = new MyLinkedList();

 * int param_1 = obj.get(index);

 * obj.addAtHead(val);

 * obj.addAtTail(val);

 * obj.addAtIndex(index,val);

 * obj.deleteAtIndex(index);

 */

206.反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

本题我们可以从题目要求入手，对链表进行一个模拟。不难看出我们需要将后一个节点指向前一个节点 ，在此基础上我们还要解决一个问题：我们以样例来说明，当我们将节点2指向节点1时，我们应该怎么移动当前指针到下一个节点。

显然，我们可以定义一个变量next来预先存储节点2的next指针即可。另一个问题是如何让节点1指向null，参考之前说过的操作引入一个哨兵节点，这样pre指针指向哨兵节点，cur指针指向头结点。在最开始我们就能让头节点指向null。

代码

1.双指针写法

class Solution {

    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;

    }

}

2.递归写法

class Solution {

    public ListNode reverseList(ListNode head) {

        return reverse(head, null);

    }

    // 关于cur为什么为空 ， 因为我们返回的是pre，如果cur == null 时 pre才指向最后一个链表的元素

    public ListNode reverse(ListNode cur, ListNode pre) {

        if (cur == null) return pre;

        ListNode next = cur.next;

        cur.next = pre;

        return reverse(next, cur);

    }

}

24. 两两交换链表中的节点

题意：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

思路

拿到一道题目我们看完题干和数据范围后，一定先自己动手模拟一下，理清楚题目要求，也能方便我们将模拟操作抽象为具体的代码。

下面是根据样例我们模拟的过程：

在图片中上面的链表是初始时的链表，下面的链表为我们的目标链表。

可以看出如果要得到目标链表我们必须得进行三个步骤：

将哨兵节点指向节点2
将节点2指向节点1
将节点1指向节点3

在我们完成上面三个步骤后，我们将当前指针移动两位，及如果我们要操作两个节点，指针必须在这两个节点的前面一个节点。

但是当我们在改变指向以后我们就不能找到节点1和节点3了，所以我们得提前存储一下节点1和节点3,由此可知循环的条件为cur.next != null && cur.next.next != null

根据以上思路不难写出代码。

代码

class Solution {

    public ListNode swapPairs(ListNode head) {

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {

            ListNode tmp = cur.next;

            ListNode tmp1 = cur.next.next.next;

            cur.next = cur.next.next;

            cur.next.next = tmp;

            cur.next.next.next = tmp1;

            cur = cur.next.next;

        }

        return dummy.next;

    }

}

19.删除链表的倒数第N个节点

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

进阶：你能尝试使用一趟扫描实现吗？

示例：

思路

首先，最暴力的思路就是遍历一遍统计链表长度，再遍历一遍删除倒数第N个节点，这种思路的代码实现简单，我们不在此给出。

我们考虑如何使用一趟扫描实现此功能，在这里我们引入一个快慢指针的思想。

我们设置两个指针他们的起点都为哨兵节点，其中快指针fast每次先移动n位，然后快慢指针才一起开始移动，当快指针到达链表末尾的时候，慢指针刚好指向我们要删除的倒数第N个节点的前一个节点。

如下图所示：

所以循环的结束条件为fast走到最后时，及cur.next != null

代码

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode fast = dummy;

        ListNode slow = dummy;

        while (n -- > 0) fast = fast.next;

        while (fast.next != null) {

            fast = fast.next;

            slow = slow.next;

        }

        slow.next = slow.next.next;

        return dummy.next;

    }

}

160.链表相交

题意：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

示例：图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

示例 1：

示例 2：

示例 3：

思路

首先本题不是比较的val值相同，而是比较的节点相同，及val和next都相同。

明确了这一点之后我们继续讨论如何解决该问题，由于给出的两个链表可能长度并不相同，所以我们应该让两个链表从相同长度的位置开始进行比较。

所以我们先得到两个链表的长度，再让长的链表先前进两个链表之间的差值的距离。

这样我们就可以从相同位置开始进行比较，当比较到两个节点相同的时候，即找到了相交的节点返回即可，当循环结束时还没有找到则没有相交的节点。

while循环的条件不难得出为cur != null

代码

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode curA = headA;

        ListNode curB = headB;

        int lenA = 0, lenB = 0;

        int len;

        while (curA != null) {

            lenA ++;

            curA = curA.next;

        }

        while (curB != null) {

            lenB ++;

            curB = curB.next;

        }

        // 找出长度大的那个链表

        curA = headA;

        curB = headB;

        if (lenB > lenA) {

            int tmp = lenA;

            lenA = lenB;

            lenB = tmp;

            curA = headB;

            curB = headA;

        }

        // 让长的先走

        len = lenA - lenB;

        while (len -- > 0) curA = curA.next;

        while (curA != null) {

            if (curA == curB) return curA;

            curA = curA.next;

            curB = curB.next;

        }

        return null;

    }

}

142.环形链表II

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思路

首先要解决题目要求的问题，我们可以将其转换为解决两个子问题

子问题1：然后判断有环

在这里我们也引入一个快慢指针，快指针每次走两步，慢指针每次走一步。当链表中存在环的时候，快指针和慢指针一定会相遇。

子问题2：如何找到环的起点

根据子问题1得到的相遇的节点，我们用index表示，同时我们定义一个index1在头结点的位置，然后让两个节点一起走，当他们相遇的时候的节点即为环开始的节点。

具体证明请看：代码随想录

while 循环的条件为fast != null && fast.next != null

代码

public class Solution {

    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;

        ListNode slow = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

            if (slow == fast) {

                ListNode idx = fast;

                ListNode idx1 = head;

                while (idx != idx1) {

                    idx = idx.next;

                    idx1 = idx1.next;

                }

                return idx;

            }

        }

        return null;

    }

}

巴特西

代码随想录-day1

链表