数据结构--链表(java)

2018-09-08 本文已影响207人凯玲之恋

一简介

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。
image

1.1 结点结构

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

1.2 操作

与数组不同，我们无法在常量时间内访问单链表中的随机元素。
如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

1.3 添加操作 - 单链表

如果我们想在给定的结点 prev 之后添加新值，我们应该：

1. 使用给定值初始化新结点 cur；
1. 将 cur 的“next”字段链接到 prev 的下一个结点 next；
1. 将 prev 中的“next”字段链接到 cur 。

与数组不同，我们不需要将所有元素移动到插入元素之后,因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

1.4 删除操作 - 单链表

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

1. 找到 cur 的上一个结点 prev 及其下一个结点 next；
1. 接下来链接 prev 到 cur 的下一个节点 next。
第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

1.5 设计链表

设计链表的实现。您可以选择使用单链表或双链表。

单链表中的节点应该具有两个属性：val 和 next。
- val 是当前节点的值
- next 是指向下一个节点的指针/引用

如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：

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

二双指针技巧

2.1 给定一个链表，判断链表中是否有环。

可能已经使用哈希表提出了解决方案

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
这正是我们在链表中使用两个速度不同的指针时会遇到的情况：
- 1. 如果没有环，快指针将停在链表的末尾。
- 1. 如果有环，快指针最终将与慢指针相遇。

所以剩下的问题是：这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
亲参考2.2图

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

2.2 返回链表开始入环的第一个节点

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

解题，有了2.1的基础，来计算一下。

QQ截图20180908102303.png

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                break;
            }
        }

        while (head != null && slow != null) {
            if (head.equals(slow)) {
                return slow;
            }
            head = head.next;
            slow = slow.next;
        }

        return null;

    }
}

2.3 相交链表

(判断是否相交，可以遍历两个链表，看最后一个节点是否相等)
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始相交。
注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

    /**
     * 返回相交单向链表的交点
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        //记录链表的长度
        int lenA = 1;
        ListNode tempA = headA;
        while (tempA.next != null) {
            lenA++;
            tempA = tempA.next;
        }

        int lenB = 1;
        ListNode tempB = headB;
        while (tempB.next != null) {
            lenB++;
            tempB = tempB.next;
        }

        //判断链表是否相交，不想交直接返回null
        if (!tempA.equals(tempB)) {
            return null;
        }

        //截取后半段，相同长度的链表
        int reduseCount = lenA - lenB;

        tempA = headA;
        tempB = headB;
        if (reduseCount > 0) {
            for (int i = 0; i < reduseCount; i++) {
                tempA = tempA.next;
            }
        } else {
            reduseCount = Math.abs(reduseCount);
            for (int i = 0; i < reduseCount; i++) {
                tempB = tempB.next;
            }
        }

        //循环遍历找到交点
        while (tempB != null && tempA != null) {
            if (tempB.equals(tempA)) {
                return tempB;
            }
            tempA = tempA.next;
            tempB = tempB.next;
        }

        return null;
    }

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
解题思路
- 典型的利用双指针法解题。首先让指针first指向头节点，然后让其向后移动n步，接着让指针sec指向头结点，并和first一起向后移动。当first的next指针为NULL时，sec即指向了要删除节点的前一个节点，接着让first指向的next指针指向要删除节点的下一个节点即可。
- 注意如果要删除的节点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。

    /**
     * 删除链表的倒数第 n 个节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        if (n == 0) {
            return null;
        }

        ListNode first = head;
        ListNode sec = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }

        while (first != null && first.next != null) {
            first = first.next;
            sec = sec.next;
        }

        if (sec.next == null) {
            return null;
        }


        sec.next = sec.next.next;
        return head;
    }

2.5小结

2.5.1 提示

1. 在调用 next 字段之前，始终检查节点是否为空。
- 获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
1. 仔细定义循环的结束条件。

2.5.2 复杂度分析

空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。

三经典问题

3.1 反转链表

一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。
单链表--反转

3.2 删除链表中的节点

删除链表中等于给定值 val 的所有节点。
示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

代码

    /**
     * 删除链表中的节点
     */
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        //定义前指针 是为了删除节点
        ListNode pre = null;
        
        //定义next是为了指针后移
        ListNode next;
        
        for (ListNode i = head; i != null; i = next) {
            next = i.next;
            if (i.val == val) {
                //这个判断说明头一个节点，就需要删除，因此头指针后移
                if (head.equals(i)) {
                    head = head.next;
                }

                //前节点next指向后节点
                if (pre != null) {
                    pre.next = i.next;
                }

                i.next = null;
            } else {
                pre = i;
            }
        }

        return head;
    }

3.3 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:

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

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
代码

    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;


        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

3.4 回文链表

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

    /**
     * 断一个链表是否为回文链表
     * 输入: 1->2->2->1
     * 输出: true
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode reverseNode = null;//指向反转的链表
        ListNode nomalNode;//指向后面后半截链表

        if (head.next.next == null) {
            reverseNode = head;
            nomalNode = head.next;
            reverseNode.next = null;
        } else {
            //快慢指针找中间值
            //顺便反转前半截链表
            ListNode slow = head;
            ListNode fast = head;

            ListNode tempSlow;
            ListNode tempFast;


            while (fast.next != null && fast.next.next != null) {
                tempSlow = slow.next;
                tempFast = fast.next.next;

                slow.next = reverseNode;
                reverseNode = slow;

                slow = tempSlow;
                fast = tempFast;
            }


            tempSlow = slow.next;
            slow.next = reverseNode;
            reverseNode = slow;


            //考虑链表是奇数长度链表
            if (fast.next == null) {
                reverseNode = reverseNode.next;
            }

            nomalNode = tempSlow;
        }

        //遍历后半截找不同
        while (nomalNode != null && reverseNode != null) {
            if (nomalNode.val != reverseNode.val) {
                return false;
            }
            nomalNode = nomalNode.next;
            reverseNode = reverseNode.next;
        }

        return true;

3.5 小结

快慢指针：可以找环，可以找中间点，可以相差n个节点的链表

四双链表

4.1 简介 - 双链表

4.1.1 定义

双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

image

4.1.2 结点结构

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;
    DoublyListNode(int x) {val = x;}
}

与单链接列表类似，我们将使用头结点来表示整个列表。

4.1.3 操作

与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。

我们不能在常量级的时间内访问随机位置。
我们必须从头部遍历才能得到我们想要的第一个结点。
在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。

4.2 添加操作 - 双链表

如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：

链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；

image
用 cur 重新链接 prev 和 next。

image

4.3 删除操作 - 双链表

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是O(1)。

五、小结 - 链表

5.1 小结

5.1.1 回顾

让我们简要回顾一下单链表和双链表的表现。
它们在许多操作中是相似的。

它们都无法在常量时间内随机访问数据
它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
它们都能够在 O(1) 时间内删除第一个结点

但是删除给定结点(包括最后一个结点)时略有不同。

在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

5.1.2 对照

这里我们提供链表和其他数据结构（包括数组，队列和栈）之间时间复杂度的比较：

image
经过这次比较，我们不难得出结论：

如果你需要经常添加或删除结点，链表可能是一个不错的选择。
如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

5.2 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

   /**
     * 合并两个有序链表
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        ListNode mergeListNode;
        if (l1.val > l2.val) {
            mergeListNode = l2;
            temp2 = l2.next;
        } else {
            mergeListNode = l1;
            temp1 = l1.next;
        }
        ListNode mergeListNodePointer = mergeListNode;


        //每次循环只前进一个指针
        while (temp1 != null && temp2 != null) {
            if (temp1.val > temp2.val) {
                mergeListNodePointer.next = temp2;
                mergeListNodePointer=mergeListNodePointer.next;
                temp2 = temp2.next;
            } else {
                mergeListNodePointer.next = temp1;
                mergeListNodePointer=mergeListNodePointer.next;
                temp1 = temp1.next;
            }
        }

        //将剩余的节点拼接起来
        if (temp1 != null) {
            mergeListNodePointer.next = temp1;
        }

        if (temp2 != null) {
            mergeListNodePointer.next = temp2;
        }

        return mergeListNode;
    }

5.3 两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

参考

链表
 https://www.jianshu.com/p/ef71e04241e4

数据结构--链表(java)

一简介

1.1 结点结构

1.2 操作

1.3 添加操作 - 单链表

1.4 删除操作 - 单链表

1.5 设计链表

二双指针技巧

2.1 给定一个链表，判断链表中是否有环。

2.2 返回链表开始入环的第一个节点

2.3 相交链表

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

2.5小结

2.5.1 提示

2.5.2 复杂度分析

三经典问题

3.1 反转链表

3.2 删除链表中的节点

3.3 奇偶链表

3.4 回文链表

3.5 小结

四双链表

4.1 简介 - 双链表

4.1.1 定义

4.1.2 结点结构

4.1.3 操作

4.2 添加操作 - 双链表

4.3 删除操作 - 双链表

五、小结 - 链表

5.1 小结

5.1.1 回顾

5.1.2 对照

5.2 合并两个有序链表

5.3 两数相加

参考

猜你喜欢

热点阅读

数据结构--链表(java)

一 简介

1.1 结点结构

1.2 操作

1.3 添加操作 - 单链表

1.4 删除操作 - 单链表

1.5 设计链表

二 双指针技巧

2.1 给定一个链表，判断链表中是否有环。

2.2 返回链表开始入环的第一个节点

2.3 相交链表

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

2.5小结

2.5.1 提示

2.5.2 复杂度分析

三 经典问题

3.1 反转链表

3.2 删除链表中的节点

3.3 奇偶链表

3.4 回文链表

3.5 小结

四 双链表

4.1 简介 - 双链表

4.1.1 定义

4.1.2 结点结构

4.1.3 操作

4.2 添加操作 - 双链表

4.3 删除操作 - 双链表

五、小结 - 链表

5.1 小结

5.1.1 回顾

5.1.2 对照

5.2 合并两个有序链表

5.3 两数相加

参考

猜你喜欢

热点阅读

一简介

二双指针技巧

三经典问题

四双链表