算法
算法

经典算法-链表

相交链表

  • 暴力求解：双重循环将A中每个节点与B中比较
  • Hash表：将A中节点存入Hash表中，再遍历B去Hash表里判断，时间复杂度O(n)
  • 双指针： 链表遍历两次长度是一样，当链表完成后交换指针
  • 计算出两个链表的长度差值N，先将长链表的指针移动先N个位置，再同步遍历
1
2
3
4
5
6
7
8
9
10
11
12
// 160. 相交链表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pA = headA, pB = headB;
    while (pA != pB) { // 链表遍历两次长度是一样的
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

链表两两交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode swapPairs(ListNode head) {
    ListNode preHead = new ListNode(-1), curr = preHead;
    preHead.next = head;
    while (curr.next != null && curr.next.next != null) {
        ListNode node1 = curr.next;
        ListNode node2 = curr.next.next;
        curr.next = node2;
        node1.next = node2.next;
        node2.next = node1;
        curr = node1;
    }
    return preHead.next;
}

public ListNode swapPairsV2(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = head.next;
    head.next = swapPairsV2(newHead.next);
    newHead.next = head;
    return newHead;
}

删除链表倒数第N个节点

链表倒数第N个节点，可以使用双指针，先将其中一个指针前移动N-1次，然后再一起移动两个指针，当其中一个指针指向最后一个位置时，另一个指针则指向倒数第N个节点；

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
// 双指针
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = head;
    ListNode second = dummy;
    for (int i = 0; i < n; ++i) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    ListNode ans = dummy.next;
    return ans;
}
// 迭代
public ListNode removeNthFromEnd(ListNode head, int n) {
    int nth = removeNthFromEndDfs(head, head.next, n);
    return nth > 1 ? head.next : head;
}

public int removeNthFromEndDfs(ListNode before, ListNode curr, int n) {
    if (curr == null) {
        return n + 1;
    }
    int nth = removeNthFromEndDfs(curr, curr.next, n) - 1;
    if (nth == 1) {
        before.next = curr.next;
    }
    return nth;
}

链表反转

1
2
3
4
5
6
7
8
9
10
// 206. 反转链表
static class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
迭代
1
2
3
4
5
6
7
8
9
10
public ListNode iterate(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next; // 将下一个节点指针保存到next变量 next = curr.next
        curr.next = prev; // 将下一个节点的指针指向prev，curr.next = prev
        prev = curr;	// 准备处理下一个节点，将curr赋值给prev
        curr = next;	// 将下一个节点赋值为curr，处理一个节点
    }
    return prev;
}
递归
1
2
3
4
5
6
7
8
9
10
public ListNode recursion(ListNode head) {
    // 为了保证链不断，必须从最后一个元素开始
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = recursion(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

环形链表

判断链表中是否有环

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
// 141. 环形链表
public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<ListNode>();
    while (head != null) {
        if (!seen.add(head)) {
            return true;
        }
        head = head.next;
    }
    return false;
}

// 环形链表 II：返回链表开始入环的第一个节点
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;
}
双指针

设链表中环外部分的长度为a，slow指针进入环后，又走了b的距离与fast指针相遇，fast 指针已经走完了环的n圈，环的节点数为b+c，因此它走过的总距离为 a+b+n(b+c)=a+(n+1)b+nc；fast指针走过的距离为slow指针的2倍即2(a+b)，故a=c+(n−1)(b+c)；故从相遇点到入环点的距离加上n−1圈的环长，恰好等于从链表头部到入环点的距离

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
43
44
// 141. 环形链表
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

// 环形链表 II：返回链表开始入环的第一个节点
public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    boolean loopExists = false;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            loopExists = true;
            break;
        }
    }

    if (loopExists) {
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    return null;
}

链表的中间节点

通过快慢指针，快指针每次移动2个节点，遍历结束条件是快指针或快指针下一个节点为空，若节点数为奇数则快指针最后指向最后一个节点，若为偶数则快指针指向null

1
// 876. 链表的中间结点

回文链表

  • 通过数组：先将链表拷贝到数组，在通过双指针遍历数组
  • 快慢指针：快指针每次移动2个节点，当快指针到尾部的时候，慢指针刚好到中间位置，反转链表，将快指针移动到原始链表头部再跟反转链表挨个比较，要考虑奇偶数节点数
1
// 234. 回文链表