Algorithm

本周做的算法题是 141. Linked List Cycle。

问题描述

给定一个单链表，判断是否其是否存在环路。

思路

  1. 将要删除的节点之后向节点的值赋值到删除的节点移动，后续的节点补上，若删除是倒数第二个节点，时间复杂度为 O(n-1), 其中n为链表的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void deleteNode(ListNode node) {
    if (null == node) {
        return;
    }
    while (node != null && node.next != null) {
        node.val = node.next.val;
        // delete duplicate last node，
        if (node.next.next == null) {
            node.next = null;
        } else {
            node = node.next;
        }	
    }
}
  1. 将要删除的节点的值替换为后面一个节点的值，然后删除节点下一个指针，指向删除节点的下一个节点再下一个节点。时间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
public void deleteNode(ListNode node) {
    if (null == node) {
        return;
    }
    
    node.val = node.next.val;
    
    // node.next = node.next.next;
    ListNode nextNode = node.next;
    node.next = nextNode.next;
    nextNode = null;
}

Review: 每周一篇英文文章

Tip

Share