Python面试——剑指offer&leedcode刷题整理（链表）_python pa=pa==none?headb:pa.next

1、相交链表

leetcode 160题

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        pa = headA
        pb = headB
        while pa is not pb:
            #若无交点，则在none处相遇，退出循环
            if pa == None:
                pa = headB
            else:
                pa.next
            if pb == None:
                pb = headA
            else:
                pb.next
        return pa

2、环形链表

leetcode 141题

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解法

判断链表中是否是有环，采用追赶法的思路，设置一个walker，每次走一步，设置一个runner，每次跑两步，当runner追上walkder时，说明链表中有环存在。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and slow and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

3、合并两个有序链表

leetcode 21

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解法

很简单的链表拼接题，但是要注意两个地方
1、返回值要返回head.next
2、无需判断循环后哪个不为空，or返回第一个为真的值

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
 
        head = ListNode(0)  #创建一个新的头节点
        current_node = head  #新链表的当前节点
        while l1 != None and l2 != None:   #l1和l2 存在
            if l1.val > l2.val:  #l1值大于l2，将l2值插进来，遍历l2
                head.next = l2
                l2 = l2.next
            else :
                head.next = l1
                l1 = l1.next
            head = head.next #一次比较后，继续遍历
        if l1 == None:
            head.next = l2
        elif l2 == None:
            head.next = l1
        return current_node.next

4、删除链表中的重复元素

leetcode 83题

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

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        p = head
        q = head.next
        while q:
            if p.val == q.val:
                p.next = q.next
                q = q.next
            else:
                p = p.next
                q = q.next
        return head

法二：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur.next = cur.next.next
            cur = cur.next
        return head

5、移出链表元素

leetcode 203

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解法

"有了第83题的思路，我们这里可以用一个指针来进行链表的遍历，但是这里需要注意的是，头节点也需要进行判断，如果头节点的值等于val的话，我们不能返回头节点，所以这里很巧妙的重新生成了一个无关的头节点。

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        cur = dummy
        while cur:
            while cur.next and cur.next.val == val:
                cur.next = cur.next.next
            cur = cur.next
        return dummy.next

6、翻转链表

leetcode 206

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解法

链表转置，这里实在想不到一个指针的解法了，只能用两个指针，再加上head的帮忙，p指针记录的是每次的队头元素，q指针指向下一个要插入队头的元素。

可参考：https://blog.csdn.net/feliciafay/article/details/6841115

方法一：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return None
        p = head
        q = head.next
        head.next = None
        while q:
            r = q.next
            q.next = p
            p = q
            q = r
        head = p
        return head

方法二：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return None
        if head.next == None:
            return head
        p = head.next
        while p.next != None:
            q = p.next
            p.next = q.next
            q.next = head.next
            head.next = q
        p.next = head
        head = p.next.next
        p.next.next = None
        return head