14. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
思路： 设置两个指针指向链表第一个节点，指针1往后遍历至第k个节点时，指针2开始往后遍历，当指针1走到链表末尾的时候，指针2此时指向倒数第k个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode ptr1 = head, ptr2 = head;
int count = 0;
while(ptr1!=null){
ptr1 = ptr1.next;
if(count < k) count++;
else if(count == k) ptr2 = ptr2.next;
}
return count < k? null: ptr2;
}
}
15. 反转链表
输入一个链表，反转链表后，输出链表的所有元素。
思路： 递归至链表尾部，将链表尾部的指针指向前一个节点，再断裂原先的指向，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode output = ReverseList(head.next);
head.next.next = head;
head.next = null;
return output;
}
}
16. 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路： 新建链表，若排序链表1的第一个节点小于排序链表2的第一个节点，则新链表存取链表1的第一个节点，并将链表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
26
27
28
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode res = new ListNode(0);
ListNode ptr = res;
while(list1 != null && list2 != null){
if(list1.val >= list2.val){
ptr.next = list2;
list2 = list2.next;
}
else{
ptr.next = list1;
list1 = list1.next;
}
ptr = ptr.next;
}
ptr.next = list1 == null? list2: list1;
return res.next;
}
}