Miraisen
0%

LeetCode链表篇

发表于 更新于 分类于
本文字数： 926 阅读时长 ≈ 1 分钟

160.相交链表

要找出并返回两个单链表相交的起始节点。

img

a2和b3可能值相等，但节点在内存中指向的是不同的位置，因此仍然是不同的节点。

读题后思路是用双指针一个一个比较，但具体比较的应该是内存中存储的是同一个位置的第一个节点即为答案。根据链表结构，node.next指的是下一个节点的指针。故比较这个值是否相等即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        h1 = headA
        h2 = headB
        while(h1):
            while(h2):
                if h1 == h2:
                    return h1
                else:
                    h2 = h2.next
            h1 = h1.next
            h2 = headB
        return None

超时了，学习题解：

1
2
3
4
5
6
7
8
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        h1 = headA
        h2 = headB
        while h1 != h2:
            h1 = h1.next if h1 else headB
            h2 = h2.next if h2 else headA
        return h1

思路是:

Picture1.png

A先遍历完链表headA，再开始遍历链表headB，当走到node时，共走步数a+b-c，同理，B走到公共节点时共走步数b+a-c。

如果有公共尾部，c>0；如果没有公共尾部，c=0。A和B同时指向null

237.删除链表中的节点

1
2
node.val = node.next.val
node.next = node.next.next

如果头节点可能被删除或修改，加个dummy会很方便

1
dummy = ListNode(next = head)
1
ListNode dummy = new ListNode(0, head);