链表中环的问题和双相链表

Posted on Edited on In ,

算法通关村第一关——链表中环的问题和双相链表

在操作系统、JVM等基础框架中运用广泛

1. 链表中的环问题

  1. 如何确定链表中存在环
  2. 假如环存在，如何确定环的入口
  3. 理解双向链表的含义和操作方法

1.1. 如何确定链表中是否有环（LeeCode141）

  • 如何确定链表中是否有环（LeeCode141）
  • 有环的话环在哪里（LeeCode142）
方法一、运用hash，将要遍历的元素放入map中
1
2
3
4
5
6
7
8
9
10
class Solution:
	def hasCycle(self,head):
        #python
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
       return False#python
1
2
3
4
5
6
7
8
9
10
11
12
13
var hasCycle = function(head) {
    //js
    seen = new Set()
    while(head){
        if(seen.has(head)){
            return true
        }else{
            seen.add(head)
            head = head.next
        }
    }
    return false
};
方法二、双指针法：

一个指针走一格，一个指针走两格，只要快指针遇上慢指针，那么就有环

1
2
3
4
5
6
7
8
9
10
11
var hasCycle = function (head) {
  let fast = head, slow = head
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
    if (fast === slow) {
      return true
    }
  }
  return false
};//js
方法三、 标记法
1
2
3
4
5
6
7
8
9
10
11
const hasCycle = function(head) {
  while (head) {
    if (head.tag) {
      return true;
    }
    head.tag = true;
    head = head.next;
  }
  return false;
};

方法四以上：还有一些邪门的方法(js是这样的)
1
2
3
4
5
6
7
8
var hasCycle = function (head) {
    try {
        JSON.stringify(head)
    } catch{
        return true
    }
    return false
};

1.2.有环的话环在哪里（LeeCode142）

方法一、标记法
1
2
3
4
5
6
7
8
9
10
11
var detectCycle = function (head) {
    while (head) {
        if (head.tag) {
            head.tag = null
            return head
        }
        head.tag = true
        head=head.next
    }
    return null
};
方法二、双指针法

双指针可以计算出相遇位置距离入口位置的距离

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast,slow=head,head
        while True:
            if not(fast and fast.next):return
            fast,slow=fast.next.next,slow.next
            if fast ==slow:break
        fast =head
        while fast!=slow:
            fast,slow=fast.next,slow.next
        return fast

2. 双向链表

解释：可以向前也能向后

2.1 基础

1
2
3
4
5
class Node():
	def __init__(self,elem):
		self.pre = None #前
		self.elem = elem
		self.next = None #后

结构和遍历方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def length(self):
    #链表长度
    if self.is_empty():
        return 0;#判断为空
    count = 0
    cur = self.__head
    while cur.next is not None:
        count += 1
        cur = cur.next
   	return count

def travel(self);
	#遍历链表
    if self.is_empty():
        return
    cur = self.__head
    while cur.next is not None;
    	print(cur.elem)
        cur = =cur.next
    print(cur.elem)

2.2 插入元素

可想而知，双向链表插入需要知道前后内容

在第一个插入和最后一个插入的两种情况，就比较方便。但如果是在中间插入就得动四条线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def add(self,item):
    #链表头部加入
    node = Node(item)
    if self.is_empty():
        self.__head = node#如果为空，那创建的本身就是双指针头
    else:
        node.next = self.__head 
        self.__head.pre = node.next
        self.__head = node
 
def append(self,item):
    #尾部加入
    if self.is_empty():
        self.__head = node#如果为空，那创建的本身就是双指针头
    else:
        cur = self.__head
        while cur.next is not None:
            cur = cur.next
        cur.next = node
        node.pre = cur.next

def insert(self,pos,item):
    #
    if pos <= 0:
        self.add(item)#插入头部，调用上面函数
    elif pos > self.length():
        self.append(item)#插入头部，调用上面函数
    else：
    #中间插入
    	node = Node(item)
        count = 0
        cur = self.__head
        while count < (pos-1):
            count += 1
            cur = cur.next#找到插入位置
       	#进行四个链的修改
        cur.next.pre = node
        node.next = cur.next
        cur.next =node
        node.pre = cur.next

2.3 删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def remove(self,item):
    #删除节点
    cur = self.__head
    forword = None
    #遍历链表指针
    while cur in not None:
        #如果找到了要删除的元素
        if cur.elem = item:
            # 如果是头部
            if cur == self.__head;
            	self.__head = cur.next
            else:
                forword.next = cur.next
           	return
        else:
            forword = cur
            cur = cur.next