链表相关2题

题目1描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

代码

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    """
    @param l1: ListNode l1 is the head of the linked list
    @param l2: ListNode l2 is the head of the linked list
    @return: ListNode head of linked list
    """
    def mergeTwoLists(self, l1, l2):
        # write your code here
        res = l3 = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                l3.next = l1 
                l1 = l1.next
            else:
                l3.next = l2 
                l2 = l2.next
            l3 = l3.next
        if l1:#不能用while，因为只需要判断一次即可
            l3.next = l1 
        elif l2:#不能用while，因为只需要判断一次即可
            l3.next = l2
        return res.next

题目2描述

输入一个链表，反转链表后，输出新链表的表头。

思路

代码

class Solution:
    # 返回ListNode
    def ReverseList(self, p_head):
        # write code here
        if p_head == None or p_head.next == None:
            return p_head
        l_head = None
        r_head = p_head
        while r_head:
            temp = r_head.next
            r_head.next = l_head
            l_head = r_head
            r_head = temp
        return l_head

题目3描述

输入一个链表，输出该链表中倒数第k个结点（是指节点的地址，不是指节点的值）。

代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        res = []
        while head:
            res.append(head)
            head = head.next
        if k > len(res) or k == 0:
            return
        return res[-k]

题目4描述

两个链表的第一个公共节点

思路1：

首先遍历链表，分别求出两个链表的长度，len(A),len(B),
先让快指针沿着长的那个链表走(len(A)-len(B))的距离，然后快慢指针一起走，当两者相等的时候就是要求的公共节点

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, head1, head2):
        # write code here
        if not head1 or not head2:
            return None
        pa, pb = head1, head2
        len1, len2 =0, 0 
        while pa:
            pa = pa.next
            len1 += 1
        while pb:
            pb = pb.next
            len2 += 1
        if len1 > len2:
            pa, pb = head1, head2
            d = len1 - len2
        else:
            pb, pa = head1, head2
            d = len2 - len1
        for i in range(d):
            pa = pa.next
        while pa != pb:
            pa = pa.next
            pb = pb.next
        return pa

思路2

现在有两个链表：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]，他们相交到8这个点。然后我们设置pa指向headA,pb指向headB，然后首先遍历各自的链表，如果遍历结束则转向另外一个链表遍历，你会发现在第二次遍历的时候他们就会相遇了。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, head1, head2):
        if not head1 or not head2:
            return None
        pa,pb = head1,head2
        while pa != pb:
            pa = pa.next if pa else head2
            pb = pb.next if pb else head1
        return pa