笔试总结--链表操作

109 阅读 0 评论 72 点赞

我是靠谱客的博主传统荷花，这篇文章主要介绍笔试总结--链表操作，现在分享给大家，希望可以做个参考。

1.输入一个链表，输出该链表中倒数第k个结点。

复制代码

1
2
3
4
5
6
7
8
//链表节点类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}

最简单粗暴一点的方法：先遍历一次，得到链表长度l，再遍历一次，遍历到l-k+1处的节点即为所求

复制代码

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
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int length = 1;
ListNode node = head;
if(head == null)
return null;
while(node.next != null){
length ++;
node = node.next;
}
if(k > length || k <= 0)
return null;
int count = 1;
node = head;
while(node.next != null){
if(count == length - k + 1)
return node;
else{
node = node.next;
count++;
}
}
return node;
}
}

比较聪明一点的算法是使用两个指针，先将第一个指针移动k-1步，然后两个指针同时移动，当第一个指针移动到链表结尾时，第二个指针的位置就是倒数第k个节点。如此只需遍历一遍。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p1 = head;
ListNode p2 = head;
if(head == null || k <= 0)
return null;
//先将第一个指针移动k-1步
for(int i = 1; i < k; i++){
p1 = p1.next;
if(p1 == null)
return null;
}
while(p1.next != null){
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}

2. 输入一个链表，反转链表后，输出新链表的表头。

改变指针指向，向后改为向前即可，无需新建链表，节省空间。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode current = head;
ListNode pre = null;
ListNode next = null;
while(current != null){
next = current.next;
current.next = pre;
pre = current;
current = next;
}
return pre;
}
}

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
29
30
31
32
33
34
35
36
37
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
ListNode mergeHead = null;
ListNode current = null;
while(list1!=null && list2!=null){
if(list1.val <= list2.val){
if(mergeHead == null){
mergeHead = current = list1;
list1 = list1.next;
}else{
current.next = list1;
current = current.next;
list1 = list1.next;
}
}else{
if(mergeHead == null){
mergeHead = current = list2;
list2 = list2.next;
}else{
current.next = list2;
current = current.next;
list2 = list2.next;
}
}
}
if(list1 == null){
current.next = list2;
}else{
current.next = list1;
}
return mergeHead;
}
}