算法 - 链表

算法 - 链表

基本操作

(1) 所有操作基于哑节点,无哑节点,那么就创造一个哑节点:

1
2
3
4
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode fastPointer = dummyNode;
ListNode slowPointer = dummyNode;

(2) 针对哑节点获取链表长度,注意起步条件检查的是 fastPointer.next :

1
2
3
4
5
int count = 0;
while (fastPointer.next != null) {
count++;
fastPointer = fastPointer.next;
}

翻转单链表

合并两个有序单链表

结对交换单链表

1
2
3
4
5
slow          fast
↓ ↓
[X] -> [1] -> [2] -|> [3]

fastPrev
1
2
3
4
5
slow          fastPrev
↓ ↓
[X] -> [2] -> [1] -|> [3]

fast
1
2
3
4
5
slow          fast
↓ ↓
[X] -> [2] -> [1] -|> [3]

fastPrev
1
2
3
4
5
              slow          fast
↓ ↓
[X] -> [2] -> [1] -> [3] -> [4] -|> [5]

fastPrev

链表分区

想象一下串糖葫芦的感觉:

1
2
-----[-]-[-]-[-]-[-]-[-]-[-]----->
-----[-]-[-]-[-]-[-]-[-]-[-]----->

从无序链表中移除重复节点

  • In order to remove duplicates from a linked list, we need to be able to track duplicates. A simple hash table will work well here.
1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteDups(LinkedListNode n) {
HashSet<Integer> set = new HashSet<Integer>();
LinkedListNode previous = null;
while (n != null) {
if (set.contains(n.data)) {
previous.next = n.next;
} else {
set.add(n.data);
previous = n;
}
n = n.next;
}
}

推荐文章