【LeetCode】面试算法总结@链表

面试算法总结：链表

• 1、LeetCode----206. 链表翻转
• • Solution1
  • Solution2
• 2、LeetCode----24. 两两交换链表中的节点
• • 基本思路
• 3、LeetCode----141. 环形链表
• • 基本思路
• 4、LeetCode----142. 环形链表 II
• • 基本思路

点击了解基本数据结构

1、LeetCode----206. 链表翻转

https://leetcode-cn.com/problems/reverse-linked-list/

Solution1

#基本思路
#首先将链表中的所有的数据读取存储到列表中
#然后结合ListNode，将列表的倒序填充到新的创建的链表中
#不断地插入后置节点，并不断的填充val，直至列表的所有数据填充完毕
class ListNode:
   def __init__(self, x):
       self.val = x
       self.next = None
 
class Solution1:
    def reverseList(self, head: ListNode) -> ListNode:
        answer_val = []
        if not head:
            return head
        while head:
            answer_val.append(head.val)
            head = head.next
        answer_val = answer_val[::-1]
        new_head = ListNode(answer_val[0])
        answer_val.remove(answer_val[0])
        p = new_head
        for i in answer_val:
            temp = ListNode(i)
            p.next = temp
            p = p.next   
        return new_head
           

Solution2

#基本思路
#直接利用链表的特性进行构造将链表的前驱和后继互换即可
class Solution2:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev
           

2、LeetCode----24. 两两交换链表中的节点

https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/

基本思路

#利用一个flag值将链表区分为奇数和偶数
#对链表进行分组，每两个进行一组
#不断地交换每一组中的前后两个数据
#奇数时最后一个元素不进行交换
#Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        p, v = head, None
        flag = 0
        if not head or not head.next:
            return head
        while p:
            try:
                if not flag % 2:
                    v = p.next
                    p.val, v.val = v.val, p.val
            except:
                pass
            flag += 1
            p = p.next
        return head
           

3、LeetCode----141. 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

基本思路

#利用两个指针，分别指向链表的头部，两个指针以不同的速度向前移动
#一个移动一次移动一位，一个一次移动两位
#最后判断，如果存在两个指针的后继指向同一个节点，那么说明此为循环链表。
#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
        """
        other_head = head
        while head:
            try:
                head = head.next
                other_head = other_head.next.next
                if head.next == other_head.next:
                    return True
            except:
                return False
        return False
           

4、LeetCode----142. 环形链表 II

https://leetcode-cn.com/problems/linked-list-cycle-ii/

基本思路

#利用set数据结构的唯一性，将已经访问过的数据存入的set表中
#当出现head在set表中时此时说明此节点为再次出现的节点
#所以这个节点就肯定是我们要找的环形链表的起点
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def detectCycle(self, head):
        set1=set([])
        while head not in set1:
            set1.add(head)
            if not head:
                break
            head=head.next
        return head