LinkedList 算法题大纲

  • 反转单链表
  • 判断单链表是否是回文的
  • 判断链表是否有环
  • 移除单链表倒数第N个元素
  • 合并两个排序的单链表
  • 移除重复的元素从排序的链表当中
  • 链表当中删除指定值的节点
  • 删除当前链表节点
  • 交换链表节点的位置

反转单链表

反转一个单链表:

a -> b -> c -> d 反转后

d -> c -> b -> a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
//先在循环外设置个pre指针
//循环head,每次都吧当前head的next指向pre
//最后返回pre即可
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head != null) {
ListNode tmp = head;
head = head.next;
tmp.next = pre;
pre = tmp;
}
return pre;
}
}

判断单链表是否是回文的

回文单链表如下,简单的描述回文就是正向读和逆向读是一样的就是回文:

1 -> 2 -> 3 -> 2 -> 1

解题思想:

  1. 利用快慢指针找到链表的中间元素
  2. 反转中间元素next后面是元素
  3. 比对head到中间元素以及中间元素到结尾是否相同
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
45
46
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;

while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

ListNode aft = reverse(slow.next);

while(aft != null) {
if (head.val != aft.val) {
return false;
}
head = head.next;
aft = aft.next;
}

return true;
}


private ListNode reverse(ListNode head) {
ListNode pre = null;
while(head != null) {
ListNode tmp = head;
head = head.next;
tmp.next = pre;
pre = tmp;
}
return pre;
}
}

判断链表是否有环

解题思路:

使用快慢指针解决

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head.next;
ListNode slow = head;

while (fast != slow) {
if (fast.next == null || fast.next.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}

return true;
}
}

移除单链表倒数第N个元素

解题思路:

  1. 先从head循环n次,判断是否n大于链表长度,如果大于直接返回head
  2. 如果n正好是链表长度,那么返回head的next,相当于删除第一个元素
  3. 如果n是其他情况,那么从当前位置指针向后移动,直到结尾,用另外一个head指针同时向后移动
  4. 最后把当前head指针的next元素删除掉就好
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode begin = head;
ListNode end = head;

for (int i = 0; i < n; i++) {
if (end == null) {
return head;
}
end = end.next;
}

if (end == null) {
return head.next;
}

while (end.next != null) {
begin = begin.next;
end = end.next;
}

begin.next = begin.next.next;

return head;
}
}

合并两个排序的单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
* 递归算法求解
*/
public class 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;
}
}
}

移除重复的元素从排序的链表当中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null) {
if (current.next != null && current.next.val == current.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}

链表当中删除指定值的节点

Example:

Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6

Return: 1 –> 2 –> 3 –> 4 –> 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null) {
if (head.next.val == val) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return dummy.next;
}
}

删除当前链表节点

例如: 1 -> 2 -> 3 -> 4

传入的节点是 3 ,那么指向完后列表是 1 -> 2 -> 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void deleteNode(ListNode node) {
if (node.next == null) {
node = null;
}
node.val = node.next.val;
node.next = node.next.next;
}
}

交换链表节点的位置

给定 1->2->3->4

返回 2->1->4->3

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;

while (head.next != null && head.next.next != null) {
ListNode t1 = head.next;
ListNode t2 = head.next.next;

head.next = t2;
t1.next = t2.next;
t2.next = t1;

head = head.next.next;
}

return dummy.next;
}
}

—EOF—