高频算法面试题 4.链表(link list)

• 定义
• 链表类型
• 代码实现
• 题目 [反转链表], [环形链表]

定义及操作
插入：类比火车车厢，先在要插入的位置断开连接，将链表前端连接到要插入的位置上，在将新插入的尾部指向下一个位置。O(n)
删除：将前一个数的指针直接指向下一个数。
找到第K个节点，需要O(n),因为要顺序遍历。

• 双向链表：每一个节点可以向前或向后遍历，可以到达链表头或尾。由于要维护两个节点，维护成本高一些。

#single link list
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.next = None

#double link list
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.pre = None
        self.last = None

#multiple link list, 
#eg. next[0] for left sub tree, next[1] for right sub tree -> binary tree
#Or next[] for the edge connect to current node -> graph
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.next = []

完整实现代码

class Node:

   def __init__(self,data,nextNode=None):
       self.data = data
       self.nextNode = nextNode

   def getData(self):
       return self.data

   def setData(self,val):
       self.data = val

   def getNextNode(self):
       return self.nextNode

   def setNextNode(self,val):
       self.nextNode = val

class LinkedList:

   def __init__(self,head = None):
       self.head = head
       self.size = 0

   def getSize(self):
       return self.size

   def addNode(self,data):
       newNode = Node(data,self.head)
       self.head = newNode
       self.size+=1
       return True
       
   def printNode(self):
       curr = self.head
       while curr:
           print(curr.data)
           curr = curr.getNextNode()

myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
#Output
'''Inserting
True
True
True
Printing
25
15
5'''

题目，一般考察形式：链表复杂操做（leetcode206), 考察链表自身性质，如环链表。

LC_206

• 边界条件，链表里面只有零或一个数，直接返回。

  
  
  递归算法

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

#recursive
class Solution(object):
    def reverseLlist(self, head):
        '''
        type head: ListNode
        rtype: ListNode
        '''
        #边界
        if head is None: return head
        if head.next is None: return head

        #把指向下一个的节点取出
        next_node = head.next
        #反转下一个节点开始的链表
        res = self.reverseLlist(next_node)
        #将头节点连回去
        next_node.next = head
        head.next = None
        return res

非递归解法

#非递归解法
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #边界条件
        if head is None: return head
        if head.next is None: return head
        
        #新建空结果链表
        res = None
        while not head is None:
            if res is None: 
                #如果结果链表为空，结果链表等于头结点
                res = head
                head = head.next
                res.next = None
            else:
                #如果结果链表不为空
                #先记录下一个节点
                tmp = head.next
                #将当前head连到结果链表
                head.next = res
                #更新结果链表头结点
                res = head
                #更新head
                head = tmp
            
        return res

#实例化
node_1 = ListNode(1)
node_2 = ListNode(2)
node_3 = ListNode(3)
node_4 = ListNode(4)
node_1.next = node_2
node_2.next = node_3
node_3.next = node_4
#print(node_3.next)

sol = Solution()
print(sol.reverseLlist(node_1).val)

Leetcode 142 环形链表

• 边界条件：链表为空或一个数，直接返回。
• 暴力解法：1.遍历所有节点，2.用map储存访问过的，3.若遇到访问过的则链表有环，返回该节点。-> O(n), 用到额外空间。

• 更好的解法, 问题分析 1. 链表是否有环？2. 环的入口在哪里？
  怎样知道有环，图中的这个类比方法和有意思

  
  
  两个人不断在环中转圈，速度不一样，最终会遇上。实际代码上设置两个指针，一个一次跑两个格，一个跑一个，最后会取到相同的数（撞上了）
  
  
  2n是快指针走的步数
  
  
  从上面得到两条式子，L是h到s的距离