算法通关村第一关|黄金挑战|链表中的环问题&双向链表

1.链表中环的问题

1.1 判断是否有环：使用集合处理，判断是否碰撞。

public ListNode detectCycle(ListNode head) {
	ListNode pos = head;
	Set<ListNode> visited = new HashSet<ListNode>();
	while (pos != null) {
        if (visited.contains(pos)) {
            return pos;
        } else {
            visited.add(pos);
        }
        pos = pos.next;
    }
	return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2 判断是否有环：使用快慢指针，如果有环，慢的就一定能遇到快的。

public boolean hasCycle(ListNode head) {
	if (head == null || head.next == null) {
        return false;
	}
	ListNode fast = head;
	ListNode slow = head;
	while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.3 有环时判断环的位置：使用快慢指针。

public ListNode detectCycle(ListNode head) {
	if (head == null) {
        return null;
	}
	ListNode slow = head, fast = head;
	while (fast != null) {
        slow = slow.next;
        if (fast.next != null) {
            fast = fast.next.next;
        } else {
            return null;
        }
        if (fast == slow) {
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
	return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.双向链表

2.1 双向链表的结点。

class DoubleNode {
    public int data;
    public DoubleNode next;
    public DoubleNode prev;
    public DoubleNode(int data) {
        this.data = data;
    }

    // 打印结点数据域
    public void displayNode() {
        System.out.println("{" + data + "}");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 双向链表的结构和遍历方法。

public class DoublyLinkList {
    // 分别指向双向链表的头部和尾部
    private DoubleNode first;
    private DoubleNode last;
    public DoublyLinkList() {
        first = null;
        last = first;
    }
    // 从头部开始打印
    public void displayForward() {
        System.out.println("List(first--->last):");
        DoubleNode current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }
    // 从尾部开始演绎
    public void displayBackward() {
        System.out.println("List(last--->first):");
        DoubleNode current = last;
        while (current != null) {
            current.displayNode();
            current = current.prev;
        }
        System.out.println();
    }
}
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

2.3 双向链表插入元素：在头部和尾部插入元素。

// 头部插入
public void insertFirst(int data) {
	DoubleNode newDoubleNode = new DoubleNode(data);
	if (first == null) {
        last = newDoubleNode;
    } else {
        first.prev = newDoubleNode;
    }
	newDoubleNode.next = first;
	first = newDoubleNode;
}
//尾部插入
public void insertLast(int data) {
	DoubleNode newDoubleNode = new DoubleNode(data);
    if (first == null) {
        first = newDoubleNode;
    } else {
        newDoubleNode.prev = last;
        last.next = newDoubleNode;
    }
    last = newDoubleNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.4 双向链表插入元素：在中间插入元素。

public void insertAfter(int key, int data) {
	DoubleNode newDoubleNode = new DoubleNode(data);
    DoubleNode current = first;
    while ((current != null) && (current.data != key)) {
        current = current.next;
    }
    // 当前结点current为空
    if (current == null) {
        if (first == null) {
            // 链表中没有元素，直接赋值
            first = newDoubleNode;
            last = newDoubleNode;
        } else {
            // 找不到key，在链表尾部插入新结点
            last.next = newDoubleNode;
            newDoubleNode.prev = last;
            last = newDoubleNode;
        }
    } else {// 链表中有元素，并且找到了key
        if (current == last) {
            // key与最后结点的data相等
            newDoubleNode.next = null;
            last = newDoubleNode;
        } else {
            // 两结点中间插入
            newDoubleNode.next = current.next;
            current.next.prev = newDoubleNode;
        }
        current.next = newDoubleNode;
        newDoubleNode.prev = current;
    }
}
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

2.5 双向链表删除元素：删除首尾元素。

// 删除首部元素
public DoubleNode deleteFirst() {
	DoubleNode temp = first;
    if (first.next = null) {
    	last = null;
    } else {
        first.next.prev = null;
    }
    first = first.next;
    return temp;
}

// 删除尾部元素
public DoubleNode deleteLast() {
	DoubleNode temp = last;
    if (first.next == null) {
        first = null;
    } else {
        last.prev.next = null;
    }
    last = last.prev;
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.6 双向链表删除元素：删除中间元素。

public DoubleNode deleteKey(int key) {
	DoubleNode current = first;
	while (current != null && current.data != key) {
        current = current.next;
    }
	if (current == null) {
        return null;
    } else {
        if (current == first) {
            first = current.next;
            current.next.prev = null;
        } else if (current == last) {
            last = current.prev;
            current.prev.next = null;
        } else {
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
    }
	return current;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤