链表结构
1
2
3
4
5
| class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
|
链表有一个很烦的点在于可能会对头节点进行处理。。所以时刻不能忽略头节点可能被处理的情况。
例题
在o(1)时间内删除链表节点，给定头节点和要删除节点。
- 知道要删除的节点，要从头开始遍历找到他前面的结点，才能删除该节点。
- 把要删节点的下一个节点的值赋值给要删除的节点，然后删除要删节点的下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public void deleteNode(ListNode head, ListNode node) {
if(head==null || node==null)
return;
if(node.next!=null) {
node.val = node.next.val;
node.next = node.next.next;
}
else{
ListNode pre_node = head;
while(pre_node.next!=node)
pre_node = pre_node.next;
pre_node.next = null;
}
}
|
- 题意：输入：
1->2->2->3->4->4->5 输出：1->2->3->4->5
- 从前向后遍历，设立两个指针pre， post。pre指向重复位置的第一个节点，post指向重复的最后一个节点，然后将他们相连即可。
1
2
3
4
5
6
7
8
9
10
11
12
| public ListNode deleteDuplicates(ListNode head) {
ListNode pre = head;
ListNode post = head;
while(post!=null) {
while(post.next!=null && post.val==post.next.val)
post = post.next;
pre.next = post.next;
pre = post.next;
post = post.next;
}
return head;
}
|
- 题意：输入：
1->1->2->2->3->6->4->4->5 输出：3->6->5
- 和之前的不同，这个因为要把重复的都删掉，那么头节点也会有重复的，所以要多设置一个开始节点start
- start.next = head，防止头节点被删除。
- 要学会设置计数变量，计数变量有很多好处，到处都用得到，辅助空间o(1)，还能有很大作用
- 但是这个代码的还是很耗时的，有待优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public ListNode deleteDuplicates(ListNode head) {
ListNode start = new ListNode(0);
start.next = head;
ListNode pre = start;
ListNode post = start.next;
int current_num = 1;
while(post!=null) {
while(post.next!=null && post.val==post.next.val) {
current_num += 1;
post = post.next;
}
if(current_num==1) {
pre.next = post;
pre = post;
}
post = post.next;
current_num = 1;
}
pre.next=post;
return start.next;
}
|
- 题意：输入：
1->2->3->4->5, n=2. 输出：1->2->3->5
- 因为要移除的可能是头指针，所以要定义一个指针指向头节点
- 思路1：遍历一遍，知道链表长度，第二次遍历到
length-n-1的时候，node.next = node.next.next 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0);
start.next = head;
ListNode node1 = next;
ListNode node2 = next;
int length = 0;
while(node1!=null) {
node1 = node1.next;
length += 1;
}
for(int i=0;i<length-n-1;i++) {
node2 = node2.next;
}
if(node2.next==null) return null;
else if(node2.next.next==null) node2.next = null;
else node2.next = node2.next.next;
return start.next;
}
|
- 思路2：要想只遍历一遍链表，需要定义两个指针，当第一个指针走n次之后，两个指针一起走，第一个指针指向链表尾部时，第二个链表指向要删除的前一个位置。然后
node.next = node.next.next 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0);
start.next = head;
ListNode node1 = start;
ListNode node2 = start;
for(int i=0;i<=n;i++)
node1 = node1.next;
while(node1!=null) {
node1 = node1.next;
node2 = node2.next;
}
if(node2.next.next==null) node2.next=null;
else node2.next = node2.next.next;
return start.next;
}
|
- 如果链表长度为奇数，输出中间一个：
1->2->3->4->5, 输出为：3
- 如果链表长度为偶数，输出中间两个的第二个：
1->2->3->4->5->6, 输出为：4
- 这道题和上一道题和相似，上一道题是指定第n个，这个是中间一个
- 但不同点在于，知道n就知道差几了，这个完全不知道链表长度啊！
- 快慢指针赛跑，快指针一次走两步，慢指针一次走一步，快指针到链表尾时，慢指针指向中间节点
1
2
3
4
5
6
7
8
9
| public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
|
举一反三：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些，或者让它在链表上先走若干步。
- 定义一个new_head, 用在开头，每次在new_head之后插入节点。
- Ori: 1->2->3->4
- New: new_head->1; new_head->2->1; new_head->3->2->1; new_head->4->3->2->1
1
2
3
4
5
6
7
8
9
10
| public ListNode reverseList(ListNode head) {
ListNode new_head = new ListNode(0);
while(head!=null) {
ListNode tmp = head.next;
head.next = new_head.next;
new_head.next = head;
head = tmp;
}
return new_head.next;
}
|