小桥流水78

这个屌丝很懒，什么也没留下！

热门标签

LeetCode刷题 --- 链表_head: optional[listnode]

作者：小桥流水78 | 2024-08-20 04:19:40

踩

head: optional[listnode]

定义一个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 ，请你反转链表，并返回反转后的链表。

解题：

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 的节点，并返回 新的头节点 。

定义一个头节点，和两个指针， 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 个结点，并且返回链表的头结点。

解题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 ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表

解题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 ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

解题：

参考上一题，定义哨兵节点，以及三个指针节点，仍然按照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 ，请你找出并返回链表的中间结点。

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

题解：

快慢指针法，定义两个指针，初始分别指向头节点，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的基础上改写代码


    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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/1005158