LeetCode刷题 --- 链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode刷题 --- 链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

定义一个node节点

class ListNode {
    int val;

    ListNode next;

    ListNode() {
    }

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

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

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

206 反转链表

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

LeetCode刷题 --- 链表

解题：

1、如果head为空或者只有一个节点，那么直接返回结果即可

2、否则，定义一个新链表，遍历旧链表，将每个节点插入到新链表的头部即可。

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode res = new ListNode(head.val);

        while (head.next != null) {
            ListNode next = head.next;
            head = next;

            res = new ListNode(next.val, res);

        }
        return res;
    }

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        res = ListNode(head.val)

        while head.next:
            next_node = head.next
            head = next_node

            res = ListNode(next_node.val, res)
        return res

203 根据值来删除节点

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

LeetCode刷题 --- 链表

定义一个头节点，和两个指针， p和q，如图，循环该链表：

1、如果q指针的值不等于目标值，则分别向后移动一位

2、如果q指针的值等于目标值，则p不懂，q后移，但是p仍指向q

    public List1Node removeElements(List1Node head, int val) {
        // 定义哨兵和双指针
        List1Node myHead = new List1Node(-1, head);
        List1Node p = myHead;
        List1Node q = p.next;
        while (q!=null) {
            if (q.val == val) {
                // 右指针等于目标值，q右移,p不变，但是p还指向q
                q = q.next;
                p.next = q;
            } else {
                // 两个指针均向后移动一位
                p = p.next;
                q = q.next;
            }
        }
        return myHead.next;
    }

    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        res = ListNode(-1, head)
        p = res
        q = head
        while q:
            if q.val == val:
                q = q.next
                p.next = q
            else:
                q = q.next
                p = p.next
        return res.next

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

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

LeetCode刷题 --- 链表

解题1：

1、先获取链表的长度

2、找到倒数第N个节点的前一个节点，指向下一个节点即可

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = length(head);

        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        for (int i = 1; i < length -n +1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next ==null ? null : cur.next.next;
        return dummy.next;
    }
    
    public int length(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode p = head;
        int count = 1;
        while (p.next != null) {
            p = p.next;
            count++;
        }
        return count;
    }
}

解题2

定义两个指针节点p和q，分别指向头节点，先让q节点向后移动n步，然后，在让p和q同时后移，当q指向空的时候，p恰好是倒数第n个节点的前一个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode p1 = dummy;
        ListNode p2 = dummy;

        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }

        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        p1.next = p1.next.next;
        return dummy.next;
    }
}

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        p = q = res = ListNode(next=head)
        for i in range(n):
            p = p.next

        while p.next:
            q = q.next
            p = p.next

        q.next = q.next.next
        return res.next

83、有序链表去重（留下一个）

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表

LeetCode刷题 --- 链表

解题1：

去重，可以使用Map或者set ，遍历链表，如果节点的值已经在集合中存在，那么这个节点就是重复节点，可以删除，如果不存在，则将值存入集合，继续遍历。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null){
            return head;
        }
        Set<Integer> set = new HashSet<>();
        ListNode node = head;
        set.add(node.val);
        while (node.next!=null) {
            ListNode next = node.next;
            if (set.contains(next.val)){
                node.next = next.next;
            }else {
                node = next;
                set.add(next.val);
            }
        }
        return head;
    }
}

解题2：

定义哨兵节点，和两个指针节点p/q，比较p/q的值是否相等，如果相等，q后移，p还是指向q，如果不相等，同时后移。

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-101, head);
        ListNode p = dummy;
        ListNode q = dummy.next;

        while (q != null) {
            if (q.val == p.val) {
                q = q.next;
                p.next = q;
            } else {
                q = q.next;
                p = p.next;
            }
        }
        return dummy.next;
    }

    def deleteDuplicates1(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

82. 删除排序链表中的重复元素（重复的一个不留）

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

LeetCode刷题 --- 链表

解题：

参考上一题，定义哨兵节点，以及三个指针节点，仍然按照p和q比较，遍历，多定义的r节点，是p节点的上一个节点，pq相同的时候，q不断后移，一直移到为null或者值不同，然后将r的下一个节点指向q

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-200, head);
        ListNode r = dummy;
        ListNode p;
        ListNode q;

        while ((p = r.next) != null && (q = p.next) != null) {
            if (p.val == q.val) {
                while (q != null && q.val == p.val) {
                    q = q.next;
                }
                r.next=q;
            } else {
                r = r.next;
            }
        }
        return dummy.next;
    }

    def deleteDuplicates3(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        cur = dummy = ListNode(val=-200, next=head)

        while cur.next and cur.next.next:
            val = cur.next.val
            if cur.next.next.val == val:
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy

21 合并有序链表

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

解题：

定义一个新的头节点，遍历两个链表，哪个值小，就放在新建的头节点后面。如果有一个链表为null，那就把另外一个链表的值全放在新建链表的后面。

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 头节点，及指针节点
        ListNode head = new ListNode();
        ListNode node = head;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                node.next = list1;
                list1 = list1.next;
            } else {
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        if (list1 != null) {
            node.next = list1;
        }
        if (list2 != null) {
            node.next = list2;
        }
        return head.next;
    }

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        res = head = ListNode(-100001)
        while list1 and list2:
            if list1.val <= list2.val:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next

        head.next = list1 if list1 else list2
        return res.next

23、和并多个升序链表

题解：参考21题，遍历链表，两两合并

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode node = null;
        for (int i = 0; i < lists.length; i++) {
            node = mergeTwoLists(lists[i], node);
        }
        return node;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 头节点，及指针节点
        ListNode head = new ListNode();
        ListNode node = head;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                node.next = list1;
                list1 = list1.next;
            } else {
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        if (list1 != null) {
            node.next = list1;
        }
        if (list2 != null) {
            node.next = list2;
        }
        return head.next;
    }
}

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

LeetCode刷题 --- 链表

题解：

快慢指针法，定义两个指针，初始分别指向头节点，p每次前进一步，q每次前进两步，当q前进时为null了，此时p指向的就是题目要求的中间节点。
    public ListNode middleNode(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;

        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = q = head
        while q and q.next:
            p = p.next
            q = q.next.next
        return p

243 回文链表

判断一个链表是不是回文链表，就是正读反读是一样的。

题解：

将给定的链表反转，然后将新链表和老链表逐个比较，一致则为true，否则为false。

    public boolean isPalindrome(ListNode head) {
        ListNode reverse = reverse(head);
        while (head != null) {
            if (head.val != reverse.val) {
                return false;
            }
            head = head.next;
            reverse = reverse.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode res = new ListNode(head.val);

        while (head.next != null) {
            ListNode next = head.next;
            head = next;
            res = new ListNode(next.val, res);

        }
        return res;
    }

    # 反转链表，然后一个个的比较
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        list = self.reverseList(head)
        while list:
            if list.val != head.val:
                return False
            else:
                list = list.next
                head = head.next
        return True

    # 数据放在数组中，然后反转数组，看val是否相等
    def isPalindrome1(self, head: Optional[ListNode]) -> bool:
        next_node = head
        val = []
        while next_node:
            val.append(next_node.val)
            next_node = next_node.next
        return val == val[::-1]

链表判环算法：

用快慢指针的方法（龟兔赛跑算法）：

阶段1

龟一次走一步，兔子一次走两步

兔子能走到终点，那么就不存在环

兔子能追上龟（再次相遇），说明存在环。

阶段2

再次相遇时，兔子留在原地不动，龟退回到起点

兔子和龟都每次走一步

再次相遇的时候，相遇点就是环的入口。

解释一下阶段2：

假设起点到环入口是a步，环一圈是b步

从起点开始，走a+b*n都可以到环的入口

第一次相遇：

兔走了a + m*b +k 步，k是距离环入口的距离

龟走了a + n*b +k 步，k是距离环入口的距离, m>n

兔子走的路程是龟的两倍，所以龟 = 兔 - 龟 = x*n 圈，龟走的是圈的整数倍

因为走a+b*n都可以到环的入口，因此，从相遇点开始，在走a步，就可以找到环的入口。

这个还有一个小bug，就是如果a=0，那么起点就是环入口。

141、判断是否是环形链表

根据上述判环算法，可以直接写出代码

    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        ListNode q = head;

        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
            if (q == p) {
                return true;
            }
        }
        return false;
    }

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        p1 = p2 = head
        while p1 and p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                return True
        return False

142 找到环形链表的入口

根据上述算法，可以直接在141的基础上改写代码文章来源地址https://www.toymoban.com/news/detail-449552.html

    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        ListNode q = head;

        while (q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
            if (q == p) {
                // 判断里面改写代码，将p重新指向头节点，然后两个节点每次分别走一步
                p = head;
                while (true) {
                    // 进到循环之后，先判断两个节点是否相等，
                    // 解决了头结点就是入口节点的问题。
                    if (q == p) {
                        return q;
                    }
                    p = p.next;
                    q = q.next;
                }
            }
        }
        return null;
    }

    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p1 = p2 = head
        while p1 and p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                p1 = head
                while True:
                    if p1 == p2:
                        return p1
                    p1 = p1.next
                    p2 = p2.next
        return None

到了这里，关于LeetCode刷题 --- 链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！