认识链表
链表是一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
以单链表为例，链表的存储方式如下图所示。
如上图所示，链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个链节点。为了将所有的节点串起来，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为后继指针next。
链表的几种类型：
- 单链表：每个节点有一个指针，指向自己的直接后继，但首尾不相连
- 双向链表：每个节点有两个指针，分别指向直接后继与直接前驱
- 循环链表：最后一个链节点指向头结点，形成一个环
- 双向循环链表：顾名思义，集合了双向链表与循环链表的特征
public class ListNode{
int val;
ListNode next;
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
|
移除链表元素
力扣题目链接
删除链表中等于给定值 val 的所有节点。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
|
设计链表
力扣题目链接
在链表类中实现以下功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回 -1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
}
class MyLinkedList{
int size;
ListNode head;
public MyLinkedList(){
size = 0;
head = new ListNode(0);
}
public int get(int index){
if(index < 0 || index >= size){
return -1;
}
ListNode currentNode = head;
for(int i = 0; i <= index; i++){
currentNode = currentNode.next;
}
return currentNode.val;
}
public void addAtHead(int val){
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
size++;
}
public void addAtTail(int val){
ListNode newNode = new ListNode(val);
ListNode cur = head;
while(cur.next != null){
cur = cur.next;
}
cur.next = newNode;
size++;
}
public void addAtIndex(int index, int val){
if(index > size){
return;
}
if(index < 0){
index = 0;
}
size++;
ListNode pred = head;
for(int i = 0; i < index; i++){
pred = pred.next;
}
ListNode newNode = new ListNode(val);
newNode.next = pred.next;
pred.next = newNode;
}
public void deleteAtIndex(int index){
if(index < 0 || index >= size){
return;
}
size--;
ListNode pred = head;
for(int i = 0; i < index; i++){
pred = pred.next;
}
pred.next = pred.next.next;
}
}
|
反转链表
力扣题目链接
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
|
两两交换链表中的节点
力扣题目链接
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
- 递归的思想，是链表/树题目经常遇到的，应当举一反三
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode t1 = head.next;
ListNode t2 = head.next.next;
t1.next = head;
head.next = swapPairs(t2);
return t1;
}
}
|
删除链表的倒数第N个节点
力扣题目链接
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
- 快慢指针，让快指针先走 n 步，随后快慢指针一起走
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
for (int i = 0; i < n; i++) {
cur = cur.next;
}
while (cur != null) {
cur = cur.next;
pre = pre.next;
}
pre.next = pre.next.next;
return dummy.next;
}
}
|
链表相交
力扣题目链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
- 先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中
- 判断相同、判断重复、判断包含、判断相交，哈希是常用的思想
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
|
环形链表
力扣题目链接
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
- 遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
if (visited.contains(pos)) {
return pos;
} else {
visited.add(pos);
}
pos = pos.next;
}
return null;
}
}
|
回文链表
力扣题目链接
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
list.add(cur.val);
cur = cur.next;
}
int left = 0;
int right = list.size() - 1;
while (left <= right) {
if (!list.get(left).equals(list.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
}
|
环形链表Ⅱ
力扣题目链接
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
- 快慢指针，初始都位于头部，然后开始走，直到相遇
- 相遇后将慢指针置于头节点处，然后快慢指针一起走，每次走一步，下次相遇的位置就是入口
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
}
|
8合并两个有序链表*
力扣题目链接
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ans = new ListNode();
ListNode p = ans;
ListNode st1 = list1;
ListNode st2 = list2;
while (st1 != null && st2 != null) {
if (st1.val <= st2.val) {
p.next = st1;
st1 = st1.next;
} else {
p.next = st2;
st2 = st2.next;
}
p = p.next;
}
p.next = (st1 == null ? st2 : st1);
return ans.next;
}
}
|
排序链表
力扣题目链接
给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
- 优先队列真是一个好用的东西呢（记得重写比较器）
- 优先队列中存的是节点，记得每次取出来之前将原本的 next 指针断掉，即 pre.next = null
class Solution {
public ListNode sortList(ListNode head) {
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
while (head != null) {
queue.offer(head);
head = head.next;
}
ListNode pre = new ListNode(0);
ListNode cur = pre;
while (!queue.isEmpty()) {
pre.next = queue.poll();
pre = pre.next;
pre.next = null;
}
return cur.next;
}
}
|
两数相加
力扣题目链接
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = new ListNode(0);
ListNode cur = ans;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
int num = sum % 10;
carry = sum / 10;
ListNode next = new ListNode(num);
cur.next = next;
cur = cur.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return ans.next;
}
}
|
删除链表的第N个结点
力扣题目链接
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
- 设置虚拟头结点，指向当前头结点
- 因为要删除，所以其实是找第 n 个结点的前驱节点
- 所以设置两个指针指向虚拟头结点，并让其中一个指针先走 n 步，然后两个指针一起走，直到先走的那个指针走到末尾
- 则找到了前驱
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode first = pre, end = pre;
while (n != 0) {
first = first.next;
n--;
}
while (first.next != null) {
first = first.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
}
}
|
两两交换链表中的结点
力扣题目链接
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
- 可以递归实现
- 先将 head.next 变成新头，然后修改原头的 next 指针（递归），然后拼接新头与原头
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
|