链表

2019-07-31 本文已影响0人 0200a9609930

2019-09-11更新

代码有优化, 同时增加了测试用例

不能使用struck来实现
因为next得到的只是原来的node的一个拷贝 不是指针
struct ListNode<T> {
    private var element: T
    private var next: ListNode?

    init(element: T) {
        self.element = element
    }
}

struct LinkedList {

}

https://github.com/yangyu2010/leetcode/blob/master/Swift_LeetCode/LeetCodeSwift/链表/DoubleLinkedList.swift

一. 定义

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

换成代码描述

class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None

class LinkedList:
    head: None
    tail: None

一个LinkedList类实例便代表了一个链表，它的一个实例域保存了指向链表中第一个结点的引用。如下图所示：

LinkedList-1

链表有两种类型：单链表和双链表。

LinkedList-2

LinkedList-3

二.对比数组

https://blog.csdn.net/weibo1230123/article/details/82011889

1.数组的特点

在内存中，数组是一块连续的区域。
数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。
随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
并且不利于扩展，数组定义的空间不够时要重新定义数组。

2.链表的特点

在内存中可以存在任何地方，不要求连续。
每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
增加数据和删除数据很容易。再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起。
不指定大小，扩展方便。链表大小不用定义，数据随意增删。

三.实现双向链表

class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None
        self.prev = None

class MyLinkedList:
    head = None
    tail = None

    def __init__(self):
        """
        Initialize your data structure here.

1.插入到头部

    def addAtHead(self, val: int) -> None:
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        if self.head:
            temp = ListNode(val)
            temp.next = self.head
            self.head.prev = temp
            self.head = temp
        else:
            self.head = ListNode(val)
            self.tail = self.head

2.插入到尾部

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        if self.tail:
            temp = ListNode(val)
            self.tail.next = temp
            self.tail = temp
        else:
            self.tail = ListNode(val)
            self.head = self.tail

3.插入到某个位置

    def addAtIndex(self, index: int, val: int) -> None:
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        # 小于等于0时 默认插头部
        if index <= 0:
            self.addAtHead(val)
            return

        cur = 0
        prev = self.head
        while prev:
            if cur == index - 1:
                break
            else:
                prev = prev.next
                cur += 1

        if cur != index - 1 or not prev:
            return None

        temp = ListNode(val)
        next = prev.next
        prev.next = temp
        temp.next = next

        if prev == self.tail:
            self.tail = temp

4.获取某一个

    def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if index < 0:
            return -1
        if index == 0:
            return self.head.val if self.head else -1
        temp = self.head
        cur = 0
        while temp:
            if cur == index:
                return temp.val
            temp = temp.next
            cur += 1
        return -1

5删除某一个

    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if index < 0:
            return None
        if index == 0:
            if self.head:
                self.head = self.head.next
            return None

        cur = 0
        prev = self.head
        while prev:
            if cur == index - 1:
                break
            else:
                prev = prev.next
                cur += 1

        if cur != index - 1 or not prev:
            return None

        # 如果前一个是 当前的最后一个 代表越界了
        if prev == self.tail:
            return None

        next = prev.next.next
        prev.next = next
        if next:
            next.prev = prev
        else:
            self.tail = prev

四.时间复杂度

addAtHead(e)   O(1)
addAtLast(e)   O(n)
addAtIndex(index, e) O(n)

deleteAtHead(e)    O(1)
deleteAtLast(e)      O(n)
deleteAtIndex(index, e)    O(n)

五.面试题

1. 反转链表

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

3. 环形链表I

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

4. 环形链表II

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

5. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

六.iOS运用

iOS面试中的题目要求：
实现一个 Memory Cache 类 LRUCache，使用 LRU 淘汰策略，它有容量上的限制 capacity，实现接口：

- (id)initWithCapacity:(NSInteger)capacity;
- (void)setItem:(id)item forKey:(NSString *)key;
- (id)getItemForKey:(NSString *)key;

另要求存取时间复杂度均为 O(1)

七.预习

1.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "([)]"
输出: false

示例 4:
输入: "{[]}"
输出: true

2.每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

链表