leetcode刷题-链表

链表题目汇总：

主要是发现

206

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

        return prev

141
环形链表（快慢指针）

--- hash table 
# 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
       """
       if not head or not head.next:
           return False
       
       slow = head
       fast = head.next

       while slow != fast:
           if not fast or not fast.next:
               return False
           slow = slow.next
           fast = fast.next.next
       
       return True

21
写递归

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
   def mergeTwoLists(self, list1, list2):
       """
       :type list1: Optional[ListNode]
       :type list2: Optional[ListNode]
       :rtype: Optional[ListNode]
       """
       ###### 
       if not list1  :
           return list2
       elif  not list2 :
           return list1

       if list1.val <= list2.val:
           list1.next=self.mergeTwoLists(list1.next,list2)
           return list1 
       else :
           list2.next=self.mergeTwoLists(list1,list2.next)
           return list2 

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            a = head
            b = head
            for i in range(n):
                if a.next:
                    a = a.next
                else:
                    return head.next
            
            while a.next:
                a = a.next
                b = b.next
                print(head)

            b.next = b.next.next
            print (b)
            print (head)
            return head

876

快慢指针，一个走2步，一个走1步。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        
        if not head.next:
            return head
        
        fast=head
        slow=head

        while fast.next!=None:
              if not fast.next.next : 
                  slow=slow.next
                  print slow
                  return slow
              else :
                  fast=fast.next.next
                  slow=slow.next

        return slow

---

21 合并有序链表：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        re=ListNode(0)
        if list1 == None :
            return list2
        elif list2 == None:
            return list1
        
        if list1.val <= list2.val:
            re.val=list1.val
            re.next = self.mergeTwoLists( list1.next, list2)
        else : 
            re.val=list2.val
            re.next = self.mergeTwoLists( list1, list2.next)
        
        return re
        

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list2 == nullptr ){
            return list1;
        } else if (list1 == nullptr ) {
            return list2;
        } else if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next,list2);
            return list1 ;  
        } else  {
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }  
    }
};