链表相关知识

链表

链表的定义

链表是一种通过指针串联在一起的数据结构，每个节点由两个部分组成，一个是数据域，一个是指针域（存放指向下一个地址的指针），最后一个节点的指针域为空NULL。

链表的入口节点被称为链表的头结点，即head

首先定义单个结点的结构

class ListNode:

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

单个结点中，包含了一个结点值和下一个结点的指针域

整体代码如下：

class ListNode:

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


class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head = ListNode(0)


    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.head
        for _ in range(index + 1):
            cur = cur.next
        return cur.val


    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)


    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)


    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        index = max(0, index)
        self.size += 1
        pred = self.head
        for _ in range(index):
            pred = pred.next
        to_add = ListNode(val)
        to_add.next = pred.next
        pred.next = to_add

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        pred = self.head
        for _ in range(index):
            pred = pred.next
        pred.next = pred.next.next

链表的类型

单链表

双链表

循环链表

链表的存储方式

链式存储

链表的代码定义

Java版本

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;
    }
}

Python版本

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

链表的基本操作：

• 获取链表的第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表的第index个节点前面插入一个节点
• 删除链表的第index个节点的数值

代码题

203、移除链表元素

Python代码

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        p = dummy
        while p.next:
            if p.next.val==val:
                p.next=p.next.next
            else:
                p = p.next
        return dummy.next

Java代码：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0,head);
        ListNode p = dummy;
        while(p.next!=null){
            if(p.next.val==val){
                p.next = p.next.next;
            }else{
                p = p.next;
            }
        }
        return dummy.next;
    }
}

707、设计链表

206、反转链表

本题如果重新定义一个新的链表会浪费存储空间，最好的思路是直接在链表本身上进行操作。

思路1：头插法

需要先进行判断

if not head or not head.next:
    return head

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 头插法
        p = head
        dummy = ListNode(0)
        while p:
            tmp = p.next
            p.next = dummy.next
            dummy.next = p
            p = tmp
        return dummy.next            

java代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = new ListNode();
        ListNode cur = head;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = node.next;
            node.next = cur;
            cur = tmp;
        }
        return node.next;

    }
}

思路2：双指针

从头往后进行遍历

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 双指针
        pre = None
        p = head
        while p:
            tmp = p.next
            p.next = pre
            pre = p
            p = tmp
        return pre

92、反转链表II（*）

本题和上一题的区别就在给定了需要反转的返回left到right

第一次尝试：

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 记录left到right之间的位置 然后将其逆序再反转
        dummy = ListNode(0, head)
        p = dummy
        flag = 0
        # 记录1/2/3号节点位置
        while p:
            if flag==left-1:
                cur_1 = p
                cur_2 = p.next
            if flag==right:
                cur_3 = p.next
                p.next = None
                break
            p = p.next
            flag += 1
        dummy2 = ListNode(0)
        p = cur_2
        while p:
            tmp = p.next
            p.next = dummy2.next
            dummy2.next = p
            p = tmp
        # print("cur_2:",cur_2)
        # print("dummy2:",dummy2)
        cur_1.next = dummy2.next
        cur_2.next = cur_3
        return dummy.next

在上面的过程中，遍历的时候有所重复，因此我们可以尝试只进行一次遍历节省时间开销

我们首先遍历到left前一个节点的位置，然后当前的p指针指向的就是该节点，然后继续从p.next开始进行遍历【left-right+1】次，同时记录下当前一开始的位置tail（这个位置会在最后变成第二段的最后一个节点），然后循环结束之后进行三段拼接，得到最终调整好位置的链表。

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 记录left到right之间的位置 然后将其逆序再反转
        dummy = ListNode(0, head)
        p = dummy
        for _ in range(left-1):
            p = p.next
        # p现在指向第一个中断点
        cur = p.next
        tail = cur
        prev = None
        for _ in range(right-left+1):
            tmp = cur.next
            cur.next = prev
            prev = cur # 头指针，每次都指向新插入的节点
            cur = tmp
        p.next = prev
        tail.next = cur
        return dummy.next

234、回文链表

思路：遍历一遍链表，然后使用双指针判断是否是回文的。

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        p = head
        res = []
        while p:
            res.append(p.val)
            p = p.next
        # print(res)
        return res==res[::-1]

24、两两交换链表中的节点（*）

思路就是直接修改指针

然后指针每次前进两个到下一个需要进行逆序交换的位置

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        p = dummy
        while p.next and p.next.next:
            temp = p.next
            temp1 = p.next.next.next
            p.next = p.next.next
            p.next.next = temp
            temp.next = temp1
            p = p.next.next
        return dummy.next

19、删除链表的倒数第N个节点（*）

方法一：一次遍历+再次回头

利用哈希表存储链表，然后直接取哈希表中的链表进行操作即可。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        myhash = {}
        p = dummy
        tag = 0
        while p:
            myhash[tag] = p
            p = p.next
            tag += 1
        # tag和n的关系 利用myhash
        # print(tag-n)
        if tag-n==1 and tag==2:
            return myhash[tag-1].next
        else:
            myhash[tag-n-1].next = myhash[tag-n-1].next.next
            return dummy.next

方法二：一次遍历

利用快慢指针来解决，fast指针多走n+1步，然后在没有到达末尾的情况下，slow和fast全部前进

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        slow = fast = dummy
        for i in range(n+1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

Java代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        for(int i=0;i<=n;i++){
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;        
    }
}

160、链表相交

利用哈希表来解决问题

这个方法的情况下时间空间复杂度都是O(n)级别

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        myhash = {}
        p1 = headA
        while p1:
            myhash[p1] = p1
            p1 = p1.next
        p2 = headB
        while p2:
            if p2 in myhash:
                return p2
            p2 = p2.next
        return None

Java版本代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<ListNode,ListNode> myhash = new HashMap<>();
        ListNode p = headA;
        while(p!=null){
            myhash.put(p,p);
            p = p.next;
        }
        ListNode p1 = headB;
        while(p1!=null){
            if (myhash.containsKey(p1)==true){
                return p1;
            }
            p1 = p1.next;
        }
        return null;
    }
}

141、环形链表

使用快慢指针进行判断

slow指针为慢指针，每次只走一步

fast指针为快指针，每次走两步

通过while循环，如果两个指针相遇了，说明链表中存在环，如果两个指针始终没有相遇并且fast指针到达链表的末尾了，即说明链表中不存在环。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        while slow!=fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

142、环形链表II

哈希表解决

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        myhash = {}
        p = head
        while p:
            if p in myhash:
                return p
            myhash[p] = p
            p = p.next
        return None        

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        HashMap<ListNode,ListNode> myhash = new HashMap<>();
        while(p!=null){
            if (myhash.containsKey(p)){
                return p;
            }
            myhash.put(p,p);
            p = p.next;
        }
        return null;
    }
}

双指针法：

83、删除排序链表中的重复值

本题中需要注意的是删除链表中重复元素并保留一位即可，因此不需要像82题那样在while循环中再加一个while循环来将所有的值全部删除。

注意本题中也是一样的，只有在当前结点值和下一个结点值不相等的情况下才需要移动指针。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(101, head)
        p = dummy
        while p and p.next:
            if p.val == p.next.val:
                p.next = p.next.next
            else:
                p = p.next
        return dummy.next

82、删除排序链表中的重复元素II（*）

哈希表

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        myhash = {}
        dummy = ListNode(101,head)
        p = head
        while p:
            myhash[p.val] = myhash.get(p.val,0)+1
            p = p.next
        # print(myhash)
        p = dummy.next
        prev = dummy
        while p:
            if myhash[p.val]>1:
                prev.next = p.next
            else:
                prev = p
            p = p.next
        return dummy.next        

一次遍历

注意，本题中只有p.next.val和p.next.next.val不相等的情况下，才需要移动p的指针（即在else中去移动p指针），否则就会出现的删除了前面的重复的元素，但是紧跟着的重复元素就不删除的情况，这样的写法如果测试用例中只有一处重复的元素，则不会报错。p指针只有在遇到不重复的指针的时候才进行移动。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        dummy = ListNode(101,head)
        p = dummy
        while p.next and p.next.next:
            if p.next.val == p.next.next.val:
                x = p.next.val
                while p.next and p.next.val==x:
                    p.next = p.next.next
            else:
                p = p.next
        return dummy.next

Java代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null){
            return head;
        }
        ListNode dummy = new ListNode(0,head);
        ListNode p = dummy;
        while(p.next!=null && p.next.next!=null){
            if (p.next.val==p.next.next.val){
                int x = p.next.val;
                while(p.next!=null && p.next.val==x){
                    p.next = p.next.next;
                }
            }else{
                p = p.next;
            }
        }
        return dummy.next;
    }
}