套路
- 链表问题有两种解法：1.递归 2. 两根指针
注意点
- 暂无
目录
- 合并两个排序的链表（递归）
- 从尾到头打印链表（递归）
- 删除链表中重复的结点（递归、两根指针）
合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
- 最优解：递归法是代码量最少的，本题可以用栈实现，而如果不用数据结构的话就可以用递归实现。其实本质上也是用栈实现，只不过栈变成了JVM方法栈。
private ArrayList<Integer> res = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
res.add(listNode.val);
}
return res;
}
删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null) {
return pHead;
}
if (pHead.val == pHead.next.val) {
ListNode pNode = pHead.next;
while (pNode.next != null && pHead.val == pNode.next.val) {
pNode = pNode.next;
}
return deleteDuplication(pNode.next);
} else {
pHead.next = deleteDuplication(pHead.next);
return pHead;
}
}
