1. 单链表反转
写法一：迭代版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode next = null;
while(cur != null) {
next = cur.next;
cur.next = pre; // 从前往后
pre = cur;
cur = next;
}
return pre;
}
}写法二：递归版
1
2
3
4
5
6
7
8
9
10
11class solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head; // 从后往前
head.next = null;
return newHead;
}
}
2. 链表中环的检测
写法一：哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<ListNode> ();
while(head != null) {
if(nodesSeen.contains(head)) {
retrun true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
}写法二：双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
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;
}
retrun true;
}
}
3. 两个有序的链表合并
写法一：一般写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
ListNode current = result;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return result.next;
}
}写法二：递归版本1
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
写法三：递归版本2
1
2
3
4
5
6
7
8
9
10class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head = (l1.val < l2.val) ? l1 : l2;
ListNode nonhead = (l1.val < l2.val) ? l2 : l1;
head.next = mergeTwoLists(head.next, nonhead);
return head;
}
}
4. 删除链表倒数第 n 个结点
写法：双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode left = dummy;
ListNode right = dummy;
for(int i=1; i<=n+1; i++) {
right = right.next;
}
while(right != null) {
right = right.next;
left = left.next;
}
left.next = left.next.next;
return dummy.next;
}
}
5. 求链表的中间结点
写法：快慢指针
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
6. 删除链表中的重复结点
写法一：哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null) {
return head;
}
Set<Integer> occurred = new HashSet<Integer>();
occurred.add(head.val);
ListNode pos = head;
// 枚举前驱节点
while (pos.next != null) {
// 当前待删除节点
ListNode cur = pos.next;
if (occurred.add(cur.val)) {
pos = pos.next;
} else {
pos.next = pos.next.next;
}
}
pos.next = null;
return head;
}
}- 复杂度分析
- 时间复杂度：O(N)，其中 N 是给定链表中节点的数目
- 空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N 个值
- 复杂度分析
写法二：两重循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
ListNode ob = head;
while (ob != null) {
ListNode oc = ob;
while (oc.next != null) {
if (oc.next.val == ob.val) {
oc.next = oc.next.next;
} else {
oc = oc.next;
}
}
ob = ob.next;
}
return head;
}
}- 复杂度分析
- 时间复杂度：O(N^2)，其中 N 是给定链表中节点的数目
- 空间复杂度：O(1)
- 复杂度分析