链表是空节点，或者有一个值和一个指向下一个链表的指针，因此很多链表问题可以用递归来处理。 相对来说，链表的难度不大，题目的花样不多，掌握以下这几个问题，就可以同类退出其他问题的解法。
LeetCode提供的链表结构
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
1. 找出两个链表的交点
160. Intersection of Two Linked Lists (Easy)
例如以下示例中 A 和 B 两个链表相交于 c1：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。
A: a1 → a2 d1 → d2
↘ ↗
c
↗ ↘
B: b1 → b2 → b3 e1 → e2
要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。
解题思路：
对于以下两个链表，
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
首先获取A、B两个链表各自的长度，A=5, B=6. 计算出长度差值distance=1，删除（移动）链表B前distance个节点，也就是删除b1节点。此时两个链表如下：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b2 → b3
对于处理后的链表，挨个比较链表A和链表B的各个节点，当节点相等时，即为相交节点。
代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = getNodeLength(headA);
int lenB = getNodeLength(headB);
// 得到链表后，长的链表，要移动distance到指定位置。
while (lenA - lenB > 0) {
headA = headA.next;
} else {
headB = headB.next;
}
// 得到处理后的链表A、B，然后挨个比较，判断是否相等
while (headA != null && headB != null) {
if (headA.val == headB.val) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
}
// 获取链表的长度
private void getNodeLength(ListNode head) {
int l = 0;
while (head != null) {
l++;
head = head.next;
}
return l;
}
2. 链表反转
206. Reverse Linked List (Easy)
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
解题思路：
对于每一个节点，记录下翻转前的当前节点和下一个节点，然后进行翻转。
代码：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode preNode = null;
ListNode currentNode = head;
ListNode nextNode = head.next;
while (currentNode != null) {
nextNode = currentNode.next;
currentNode.next = preNode;
preNode = currentNode;
currentNode = nextNode;
}
return preNode;
}
3. 归并两个有序的链表
21. Merge Two Sorted Lists (Easy)
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
解题思路：
使用递归，每个元素进行比较，然后.next的值通过递归确定。
代码：
// 归并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
4. 从有序链表中删除重复节点
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
解题思路：
使用递归，比较head.val == head.next.val, 相等的话，则head指向head.next
代码：
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
head.next = deleteDuplicates(head.next);
// 如果相等，指向下一个node
return head.val == head.next.val ? head.next : head;
}
5. 删除链表的倒数第 n 个节点
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || n < 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (n > 0) {
fast = fast.next;
n--;
}
// 解决n指向了最前面
//
// Input: [1], n=1
// Output: [1]
// Expected: []
if (fast == null) {
return head.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
方法二：
思路：
计算链表长度，减去n，即可获得正向的第i个节点，然后删除即可
代码：
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || n < 0) {
return head;
}
// 得到链表的长度
int len = getNodeLength(head);
ListNode newHead = head;
// 计算链表的正向第d个
int distance = len - n;
// 解决删除第一个head的问题
if (distance == 0) {
return head.next;
}
while (distance > 1) {
newHead = newHead.next;
distance--;
}
newHead.next = newHead.next.next;
return head;
}
private int getNodeLength(ListNode head) {
if (head == null) {
return 0;
}
int len = 0;
while (head != null) {
head = head.next;
len++;
}
return len;
}
6. 交换链表中的相邻结点
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
题目要求：不能修改结点的 val 值，O(1) 空间复杂度。
解题思路：
使用头指针法，虚拟出一个头指针，指向需要交换的两个几点前面
public ListNode swapPairs(ListNode head) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode pre = node;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next;
ListNode l2 = l1.next;
ListNode next = l2.next;
// 这两行的代码位置不能改变，否则会变成双向链表
l1.next = next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return node.next;
}
7. 链表求和
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
题目要求：不能修改原始链表。
解题思路：
通过stack存储链表元素，然后相加，结果存储到stack中，最终把stack转换成ListNode
代码：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
Stack<Integer> result = new Stack<>();
// 使用栈存储，逆序取出
while (l1 != null) {
s1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
s2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
// 此处的判断条件很重要
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
int v1 = s1.isEmpty() ? 0 : s1.pop();
int v2 = s2.isEmpty() ? 0 : s2.pop();
int temp = v1 + v2 + carry;
carry = temp / 10;
int val = temp % 10;
result.push(val);
}
// 将Stack转换为链表
ListNode head = new ListNode(-1);
ListNode root = head;
while (!result.isEmpty()) {
ListNode temp = new ListNode(result.pop());
root.next = temp;
root = temp;
}
return head.next;
}
8. 回文链表
234. Palindrome Linked List (Easy)
题目要求：以 O(1) 的空间复杂度来求解。
解题思路：
先获得链表长度，然后/2得到中间位置，从中间位置一分为二，后半部分存储为栈 然后前半部分与栈进行比较
代码：
public boolean isPalindrome(ListNode head) {
// 偶数的话，直接就是后半部分
// 奇数的话，是中间-1。如[1, 2, 3, 2, 1]
int n = getLen(head) / 2;
ListNode fast = head;
while (n > 0) {
fast = fast.next;
n--;
}
Stack<Integer> right = new Stack<>();
while (fast != null) {
right.push(fast.val);
fast = fast.next;
}
while (!right.isEmpty()) {
if (right.pop() != head.val) {
return false;
}
head = head.next;
}
return true;
}
private int getLen(ListNode head) {
int res = 0;
while (head != null) {
head = head.next;
res++;
}
return res;
}
