字数
1523 字
阅读时间
8 分钟
链表
结构定义
java
class ListNode {
int val;
ListNode next;
public ListNode () {}
public ListNode (int val) {
this.val = val;
}
public ListNode (int val, ListNode next) {
this.val = val;
this.next = next;
}
}虚拟节点
——删除到头节点的相关操作，设置 dummy（虚拟，哑巴——哑节点）ListNode dummy = new ListNode(-1, head);
移除链表元素
java
public ListNode removeElements (ListNode head, int val) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
// pre节点来保存变化后的值
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}设计链表
java
// 测试用例：
MyLinkedList obj = new MyLinkedList();
int param_1 = obj.get(index);
obj.addAtHead(val);
obj.addAtTail(val);
obj.addAtIndex(index,val);
obj.deleteAtIndex(index);java
// 单链表
class ListNode {
int val;
ListNode next;
ListNode () {}
ListNode (int val) {
this.val = val;
}
}
class MyLinkList {
int size;
ListNode head;
public MyLinkList() {
// 初始化 size
size = 0;
head = new ListNode(0);
}
// 获取链表中第 index 个节点的值
public int get(int index) {
if (index < 0 || index >= length) {
return -1;
}
ListNode cur = head;
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
// 添加头节点
public void addAtHead (int val) {
addAtIndex(0, val);
}
// 添加尾节点
publc void addAtTail (int val) {
addAtIndex(size, val);
}
// 在指定位置添加节点
public void addAtIndex (int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
// 留意size的更新
size++;
ListNode pre = head;
for (int i = 0; i < index; ++i) {
pre = pre.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pre.next;
pre.next = toAdd;
}
// 删除指定位置的节点,index表示第 x 个位置
public void deleteAtIndex (int index) {
if (index < 0 || index >= size) {
return;
}
// 留意size的更新
size--;
ListNode pre = head;
for (int i = 0; i < index; ++i) {
pre = pre.next;
}
pre.next = pre.next.next;
}
}反转链表
新建链表
首先想到的是定义一个新的链表，实现链表元素的反转，但是这样的空间复杂度较大
java
ListNode pHead = null;
for (ListNode p = head; p != null; p = p.next) {
pHead = new ListNode(p.val, pHead)
}
return pHead;逐个反转
难点：及时调整 cur = cur.next
java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
// 留意prev的变化
prev = curr;
curr = next;
}
return prev;
}两两交换链表中的节点
迭代调用
java
// 补充：注意node1和node2节点的暂存，否则后续置换操作会造成指针丢失
// 最后两步是 pre 和 cur 的位置改变
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}递归调用
java
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) {
return null;
}
ListNode one = head;
ListNode two = head.next;
ListNode three = two.next;
two.next = one;
one.next = swapPairs(three);
return two;
}删除链表节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
java
// 简单的node.next = node.next.next，找到N-1的节点
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int size = 0;
for (; head != null; head = head.next) {
size++;
}
ListNode cur = dummy;
for (int i = 1; i <= size - n; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}链表相交
面试题 02.07. 链表相交 - 力扣（LeetCode）
链表交点的指针不是数值相同，而是指针地址相同
解题思路:
若存在交点，则两个链表的相对末尾处必存在 curA == curB
1. 确定两个链表的长度相比大小
2. 使得链表长度短的那一方位移到与链表长的末尾处与之对应（通过长度差gap来确定位移长度）
3. 遍历末尾指针，判断是否存在相等java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
//1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
//2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}环形链表
Loading Question... - 力扣（LeetCode）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。提示：
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值为 -1 或者链表中的一个有效索引
解题思路：
- 判断链表是否有环
- 使用 fast，slow 指针（若 fast 与 slow 指针相遇。则一定有环）
- 如果有环，找到环的入口
(x + y) * 2 = x + y + n (y + z)->x = z- 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点
java
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {// 有环
ListNode index1 = fast;
ListNode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}贡献者
jiechen