链表
概述
(单)链表是由节点和指针构成的数据结构,每个节点存有一个值,和一个指向下一个节点的指针,因此很多链表问题可以用递归来处理。不同于数组,链表并不能直接获取任意节点的值,必须要通过指针找到该节点后才能获取其值。同理,在未遍历到链表结尾时,我们也无法知道链表的长度,除非依赖其他数据结构储存长度。LeetCode 默认的链表表示方法如下。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
由于在进行链表操作时,尤其是删除节点时,经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题:一是尽量处理当前节点的下一个节点而非当前节点本身,二是建立一个虚拟节点 (dummy node),使其指向当前链表的头节点,这样即使原链表所有节点全被删除,也会有一个 dummy 存在,返回 dummy->next 即可。
链表的基本操作
题解:
链表翻转是非常基础也一定要掌握的技能。我们提供了两种写法——递归和非递归,且我们建议你同时掌握这两种写法。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
21.合并两个有序链表
题解:
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode temp = new ListNode();
head = temp;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
temp.next = l1;
temp = temp.next;
l1 = l1.next;
}else{
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
}
if(l1!=null) temp.next = l1;
else if(l2!=null) temp.next = l2;
return head.next;
}
}
24.两两交换链表中的节点
题解:
利用指针进行交换操作,没有太大难度,但一定要细心。
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null) return head;
ListNode list = new ListNode();
list.next = head.next;
ListNode cur = head;
ListNode next = head.next;
while(cur!=null&&next!=null){
//交换两个结点位置
ListNode temp = next.next;
next.next = cur;
//改变第一个结点的指向
if(temp!=null&&temp.next!=null) cur.next = temp.next;
else cur.next = temp;
//将两个结点向后移动
cur = temp;
if(cur!=null) next = cur.next;
}
return list.next;
}
}
其它链表技巧
160.相交链表
题解:
假设链表 A 的头节点到相交点的距离是 a,链表 B 的头节点到相交点的距离是 b,相交点到链表终点的距离为 c。我们使用两个指针,分别指向两个链表的头节点,并以相同的速度前进,若到达链表结尾,则移动到另一条链表的头节点继续前进。按照这种前进方法,两个指针会在a + b + c 次前进后同时到达相交节点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA, l2 = headB;
while(l1!=l2){
l1 = l1==null? headB : l1.next;
l2 = l2==null? headA : l2.next;
}
return l1;
}
}
题解:
先使用快慢指针找到链表中点,再把链表切成两半;然后把后半段翻转;最后比较两半是否相等。
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(slow!=null&&fast!=null&&fast.next!=null&&fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
ListNode l2 = slow.next;
slow.next=null;
ListNode head2 = reverseList(l2);
while(head!=null&&head2!=null){
if(head.val!=head2.val) return false;
head=head.next;
head2=head2.next;
}
return true;
}
public ListNode reverseList(ListNode head){
ListNode cur = head;
ListNode pre = null;
while(cur!=null){
ListNode next = cur.next;
cur.next=pre;
pre = cur;
cur = next;
}
return pre;
}
}
练习
基础难度
83.Remove Duplicates from Sorted List (Easy)
虽然 LeetCode 没有强制要求,但是我们仍然建议你回收内存,尤其当题目要求你删除的时候。328.Odd Even Linked List (Medium)
这道题其实很简单,千万不要把题目复杂化。19.Remove Nth Node From End of List (Medium)
既然我们可以使用快慢指针找到中点,也可以利用类似的方法找到倒数第 n 个节点,无需遍历第二遍。
进阶难度
148.Sort List (Medium)
利用快慢指针找到链表中点后,可以对链表进行归并排序。