总目录
- 链表的中间节点
- 反转链表
- 回文链表
- 重排链表
- 移除链表元素
- 两两交换链表中的节点
- 合并两个有序链表
链表的中间节点-快慢指针
题号：876
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
输入：head = [1,2,3,4,5]
输出：[3,4,5]
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() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head;
ListNode q = head;
while(q != null && q.next != null){
p = p.next;
q = q.next.next;
}
return p;
}
}
|
反转链表
题号：206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
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() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode q = head;
while(q != null){
ListNode nxt = q.next;
q.next = pre;
pre = q;
q = nxt;
}
return pre;
}
}
|
回文链表
-前置 ：链表的中间节点、反转链表
题号：234
给你一个单链表的头节点 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
| class Solution {
public boolean isPalindrome(ListNode head) {
// 快慢指针
ListNode fast =head;
ListNode slow = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
// 反转
ListNode pre = null;
ListNode cur = slow;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
while (pre != null){
if(pre.val != head.val){
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
}
|
类似例题
题号：9 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isPalindrome(int x) {
if(x < 0 || x > 0 && x % 10 == 0){
return false;
}
int rev = 0;
while(rev < x / 10){
rev = rev * 10 + x % 10;
x /= 10;
}
return rev == x || rev == x / 10;
}
}
|
重排链表
题号：143
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
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
| class Solution {
public void reorderList(ListNode head) {
ListNode mid = middle(head);
ListNode head2 = reverse(mid);
while(head2.next != null){
ListNode nxt = head.next;
ListNode nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
}
private ListNode reverse(ListNode head){
ListNode pre = null, cur = head;
while(cur != null){
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
private ListNode middle(ListNode head){
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
|
移除链表元素
题号：203
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = dummy;
while(cur.next != null ){
if(cur.next.val == val){
cur.next = cur.next.next;
}
else{
cur = cur.next;
}
}
return dummy.next;
}
}
|
两两交换链表中的节点
题号：24
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [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
| class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode node0 = dummy;
ListNode node1 = head;
while (node1 != null && node1.next != null) {
ListNode node2 = node1.next;
ListNode node3 = node2.next;
node0.next = node2; // 0 -> 2
node2.next = node1; // 2 -> 1
node1.next = node3; // 1 -> 3
node0 = node1;
node1 = node3;
}
return dummy.next;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode node1 = head;
ListNode node2 = head.next;
ListNode node3 = node2.next;
node1.next = swapPairs(node3);
node2.next = node1;
return node2;
}
}
|
合并两个有序链表
题号：21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 != null ? list1 : list2;
return dummy.next;
}
}
|