链表问题总结

这篇文章将刷题以来遇到的所有链表类问题做一个总结与回顾：

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
Ying的解法：
这道题要求的是返回一个链表值的列表，而不是节点列表。因此只需要通过遍历链表，将节点值添加到列表中输出即可。

while True：技巧
链表的遍历

    def printListFromTailToHead(self, listNode):
        # write code here
        li = []
        while True:
            if listNode is None:
                break
            else:
                li.append(listNode.val)
                listNode = listNode.next
        li.reverse()
        return li

题目描述
输入一个链表，输出该链表中倒数第k个结点。
Ying的解法：
这道题要求返回的是倒数第k个节点，一种做法是：遍历一遍，将链表节点一次存入列表中，然后逆序返回第k个；如果要求空间复杂度为O(1)，则这种方法不可行，下面这种方法是合适的。
还有一种方法是维护两个相距k的指针，相当于滑动窗口，当右边的指针到达链表末尾时，前边的指针正好指向的时倒数第k个节点。

return 和return None都可以

    def FindKthToTail(self, head, k):
        # write code here
        count = 0
        node = head
        while True:
            if head:
                count+=1
                head = head.next
            else:
                break
        n = count-k+1
        if count<k:
            return None
        i = 1
        while True:
            if i<n:
                node = node.next
                i+=1
            else:
                return node

题目描述
输入一个链表，反转链表后，输出新链表的表头。
Ying的解法：
这道题等价于求反转后的链表，有两种思路：一是通过开辟辅助列表空间，一次遍历后将链表节点添加到列表中，逆序列表，然后遍历列表新建一个链表，时间复杂度O(n)，空间复杂度O(n)。二是原地反转，时间复杂度O(n)。

# 方法一：
    def ReverseList(self, pHead):
        # write code here
        li = []
        while True:
            if pHead is None:
                break
            else:
                li.append(pHead.val)
                pHead = pHead.next
        li.reverse()
        t = len(li)
        if t==0:
            return None
        else:
            listNode1 = ListNode(li[0])
            listNode3 = listNode1
            for i in range(1,t):
                listNode2 = ListNode(li[i])
                listNode1.next = listNode2
                listNode1 = listNode2
            return listNode3
# 方法二：
    def ReverseList(self, pHead):
        # write code here
        if not pHead:
            return pHead
        last = None
        while pHead:            
            tmp = pHead.next
            pHead.next = last
            last = pHead
            pHead = tmp
        return last

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
Ying的解法：
有点归并排序的感觉，时间复杂度O(m+n)

    def Merge(self, pHead1, pHead2):
        # write code here
        s = ListNode(0)
        pHead3= s
        while pHead1 and pHead2:
            if pHead1.val<pHead2.val:
                pHead3.next = pHead1
                pHead1 = pHead1.next
                pHead3 = pHead3.next
            else:
                pHead3.next = pHead2
                pHead2 = pHead2.next
                pHead3 = pHead3.next
        if pHead1:
            pHead3.next = pHead1
        elif pHead2:
            pHead3.next = pHead2
        return s.next

题目描述
输入两个链表，找出它们的第一个公共结点。
Ying的解法：
两个单向链表有公共节点，那么从第一个公共节点之后一直是重合的，即'Y'字型。两个链表可能长度不一样，那么先遍历长的，然后从剩下相同长度开始同时遍历，当遇到第一个值相等的节点时，即为找到的第一个公共节点。

链表类问题，头节点往后遍历之前，如果后续还要用到该列表，需要复制一份。

    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        len1 = 0
        len2 = 0
        ppHead1 = pHead1
        ppHead2 = pHead2
        while pHead1:
            len1+=1
            pHead1 = pHead1.next
        while pHead2:
            len2+=1
            pHead2 = pHead2.next
        if len1>len2:
            k = len1-len2
            while k>0:
                ppHead1=ppHead1.next
                k-=1
        else:
            k = len2-len1
            while k>0:
                ppHead2=ppHead2.next
                k-=1
        while ppHead1 and ppHead2:
            if ppHead1.val==ppHead2.val:
                return ppHead1
            else:
                ppHead1 = ppHead1.next
                ppHead2 = ppHead2.next
        return None

题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
Ying的解法：
开辟字典辅助空间，由于是单向链表，所以每个节点都是唯一的。在路径中，只有环的入口节点出现两次。

    def EntryNodeOfLoop(self, pHead):
        # write code here
        dict1 = {}
        dict1[pHead] = 1
        while pHead.next:
            pHead = pHead.next
            if pHead not in dict1:
                dict1[pHead] = 1
            else:
                return pHead
        return None

题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

    def deleteDuplication(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        p=ListNode(None)
        p.next=pHead
        pBefore=p
        pAfter=pHead.next
        while pHead.next!=None:
            flag=False
            while pAfter!=None and pHead.val==pAfter.val:
                if pAfter.next==None:
                    pBefore.next=None
                    return p.next
                pAfter=pAfter.next
                flag=True
            if flag:
                pBefore.next=pAfter
            else:
                pBefore=pHead
            pHead=pAfter
            pAfter=pAfter.next
        return p.next

两数相加
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
Ying的解法：
新建一个链表对结果进行存储，因为是逆序的，所以链表遍历的顺序就是加法计算的位数顺序。

考虑到两个链表长度可能不一样，类似归并排序的做法。
同时，最后一个数计算完之后可能有进位，所以作为一种情况考虑。

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        llist = ListNode(0)
        result =llist
        interval = 0
        while l1 and l2:             
            llist.next = ListNode((l1.val+l2.val+interval)%10)
            llist = llist.next
            interval = (l1.val+l2.val+interval)//10
            l1 = l1.next
            l2 = l2.next
                
        while l1:
            llist.next = ListNode((l1.val+interval)%10)
            llist = llist.next
            interval = (l1.val+interval)//10
            l1 = l1.next
        
        while l2:
            llist.next = ListNode((l2.val+interval)%10)
            llist = llist.next
            interval = (l2.val+interval)//10
            l2 = l2.next
        
        if interval!=0:
            llist.next = ListNode(interval) 
        return result.next

== 待补充==