Coding-チェーンテーブル

linklist(チェーンテーブル)
チェーンテーブルも面接でよく聞かれるテーマで、チェーンテーブルの定義は簡単で面接者のレベルを考察しやすく、例えば配列の中で簡単なテーマをチェーンテーブルに変換すると大きな変動があります.例えば、チェーンテーブルの挿入と集計並べ替え、最後からk番目のノードの検索などである.
1.回文チェーンテーブル(234)
チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください

class Solution(object):
    def isPalindrome(self, head):
        reverse, fast = None, head
        while fast and fast.next:
            fast = fast.next.next
            head.next, reverse, head = reverse, head, head.next
            
        tail = head.next if fast else head

        is_palindrome = True
        while reverse:
            is_palindrome = is_palindrome and reverse.val == tail.val
            reverse.next, head, reverse = head, reverse, reverse.next
            tail = tail.next

        return is_palindrome

2.単一チェーンテーブルの中間ノードを求める
高速、遅いポインタで実現

def find_middle_node(head):
    slow, fast = head, head
    fast = fast.next if fast else None
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

3.無秩序チェーンテーブルの重複を削除する
無秩序なチェーンテーブルが与えられ、その重複項目を除去し、元の順序、例えばチェーンテーブル1−>3−>1−>5−>5−>7を保持し、重複項目を除去した後、1−>3−>5−>7である.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        outer = head
        while outer:
            inpre = outer
            inner = inpre.next
            while inner:
                if inner.val == outer.val:
                    inner = inner.next
                    inpre.next = inner
                else:
                    inpre = inner
                    inner = inner.next
            outer = outer.next
        return head        

4.並べ替えチェーンテーブルを指定し、重複する数値を含むすべてのノードを削除する
入力:1->2->3->3->4->4->5出力:1->2->5

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteDuplicates(self, head):        
        if head is None:
            return head
        new = ListNode(None)
        new.next = head
        head = new
        outpre = head
        outer = outpre.next
        flag = False
        while outer:
            inpre = outer
            inner = inpre.next
            while inner:
                if inner.val == outer.val:
                    flag = True
                    inner = inner.next
                    inpre.next = inner
                else:
                    inpre = inner
                    inner = inner.next
            if flag:
                outer = outer.next                
                outpre.next = outer
                flag = False
            else:
                outpre = outer
                outer = outer.next
        return head.next      

        def deleteDuplicates_2(self, head):  
            if None == head or None == head.next:  
                return head  
    
            new_head = ListNode(-1)  
            new_head.next = head  
            parent = new_head  
            cur = head  
            while None != cur and None != cur.next:   
                if cur.val == cur.next.val:  
                    val = cur.val  
                    while None != cur and val == cur.val:
                        cur = cur.next  
                    parent.next = cur  
                else:  
                    cur = cur.next  
                    parent = parent.next  
    
            return new_head.next 

5.リングチェーンテーブル(141)
チェーンテーブルを指定し、チェーンテーブルにループがあるかどうかを判断し、最初の交差点の考え方を見つけます.2つのポインタslowとfastを設定し、1つのステップ長は1で、1つのステップ長は2で遍歴します.ループがあれば、slowとfastはいつもどこかで出会う.ループがない場合、fastは先に空、またはfastになります.nextが空です

class Solution(object):
    def hasCycle(self, head, firstMeetNode):
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast: #   
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                firstMeetNode = fast
                return True
        return False

6.チェーンテーブルの反転(206)
マイクロソフト入力:1->2->3->4->5->NULL出力:5->4->3->2->1->NULL

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))
        
class Solution(object):
    '''    '''
    def reverseList(self, head):
        dummy = ListNode(float("-inf"))
        while head:
            dummy.next, head.next, head = head, dummy.next, head.next
        return dummy.next        

class Solution2(object):
    '''    '''
    def reverseList(self, head):
        [begin, end] = self.reverseListRecu(head)
        return begin

    def reverseListRecu(self, head):
        if not head:
            return [None, None]

        [begin, end] = self.reverseListRecu(head.next)

        if end:
            end.next = head
            head.next = None
            return [begin, head]
        else:
            return [head, head]

7.双方向チェーンテーブルから指定した要素を削除する(マイクロソフト)

class Node(object):
    '''    '''
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

class DLinkedlist(object):
    def __init__(self):
        self._head = None
    
    def remove(self, item):
        """    """
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
#                 
                if cur.next == None:
#            
                    self._head = None
                else:
#        prev   None
                    cur.next.prev = None
#  _head       
                    self._head = cur.next
                return
            
            while cur != None:
                if cur.item == item:
#  cur       next  cur      
                    cur.prev.next = cur.next
#  cur       prev  cur      
                    cur.next.prev = cur.prev
                    break
                cur = cur.next
                

8.2つのチェーンテーブルを1つの昇順チェーンテーブルに統合する(マイクロソフト)

class Node(object):
    def __init__(self,item,next_=None):
        self.item = item
        self.next = next_
             
class Solution(object):
    def mergeTwoLists(self, l1,l2):     
        head = Node(0)
        cur = head
        while l1 != None and l2 != None:
            if l1.item <= l2.item:
                cur.next = l1
                l1 =  l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1 != None:
            cur.next = l1
        if l2 != None:
            cur.next = l2
        return head.next    

9.最後からk番目のノード
タイトル:チェーンテーブルの最後からk番目のノードを見つけて解析します:2つのポインタfastとslowを使って、fastは先にk歩を歩いて、それからfastはslowと一緒に歩いて、fastが最後のノードに着くまで、slowは最後からk番目のノードです

class Solution(object):
    '''
      ：        k   ，       。
            ，          k    ，
                        ，
                ，           k           
    '''
    def removeNthFromEnd(self, head, k):
        res = ListNode(0)
        res.next = head
        tmp = res
        for i in range(0, k):
            head = head.next
        while head != None:
            head = head.next
            tmp = tmp.next
        tmp.next = tmp.next.next
        return res.next

10.等確率でチェーンテーブルの要素を返す
題意:単鎖表をあげて、毎回確率を待ってランダムに1つの要素の分析を返します:ここではまず詳しく説明しないで、これは1つのランダム化のアルゴリズムの1種です

class Solution(object):
    def randNode(self, head):
        res = head
        cur = head.next
        i = 2
        while cur != None:
            x = random.ranint(0,int(2**31))
            j = x % i
            if j == 0:
                res = cur
            cur = cur.next
            i += 1
        return ans