链表
链表类型：单链表（只有next指针）、双链表（pre指针和next指针）、循环链表（尾节点指向头节点）
增、删、改、遍历、翻转、交换
1.设计链表707中等
class LinkedNode {
int val;
LinkedNode next;
public LinkedNode() {
}
public LinkedNode(int val) {
this.val = val;
}
}
class MyLinkedList {
// 链表的长度
private int size;
// 链表的虚拟头节点和虚拟尾节点
private LinkedNode head;
public MyLinkedList() {
size = 0;
head = new LinkedNode(0);
}
public int get(int index) {
if (index >= size) {
return -1;
}
LinkedNode cur = head.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
// 检查要插入元素索引的范围
if (index < 0 || index > size) {
return;
}
size++;
LinkedNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
LinkedNode newNode = new LinkedNode(val);
newNode.next = cur.next;
cur.next = newNode;
}
public void deleteAtIndex(int index) {
// 检查要插入元素索引的范围
if (index < 0 || index >= size) {
return;
}
size--;
LinkedNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
}
}
2.移除链表元素
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 定义虚拟头节点
ListNode newhead = new ListNode(0, head);
// pre表示前一个元素，为了删除元素后可以把链表串起来
ListNode pre = newhead;
// 循环链表的节点，判断该节点的值是否与val相等
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
// cur = cur.next;
// pre.next = cur;
pre.next = cur.next;
} else {
pre = pre.next;
// cur = cur.next;
}
cur = cur.next;
}
return newhead.next;
}
}
3.删除链表的倒数第N个结点
// // 先实现，写两次遍历，第一次记录链表的结点总个数，第二次删除；这里要防止第一次遍历结束后还能找到头
// class Solution {
// public ListNode removeNthFromEnd(ListNode head, int n) {
// // 第一次遍历
// ListNode newhead = new ListNode (-1, head);
// ListNode cur = head;
// int count = 0;
// // 第一次遍历
// while (cur != null) {
// count += 1;
// cur = cur.next;
// }
// // 第二次遍历
// // num记录要从前往后遍历到第几个位置
// int num = count - n;
// ListNode now = newhead;
// while (num > 0) {
// now = now.next;
// num -= 1;
// }
// now.next = now.next.next;
// return newhead.next;
// }
// }
// // 双指针，快慢指针，第一个指针先走n步，第二个指针留在初始位置，那么当第一个位置走到链表尾部的时候，第二个指针就处在在删除的节点位置(如果加上虚拟头节点，就是走在了要删除节点的前一个节点上)
// class Solution {
// public ListNode removeNthFromEnd (ListNode head, int n) {
// // 定义一个虚拟头节点
// ListNode newhead = new ListNode(-1, head);
// // 定义第一个节点
// ListNode first = head;
// // 定义第二个节点
// ListNode second = newhead;
// int i = 0;
// while (i < n) {
// i ++;
// first = first.next;
// }
// while (first != null) {
// first = first.next;
// second = second.next;
// }
// // 删除节点
// second.next = second.next.next;
// return newhead.next;
// }
// }
// 栈
class Solution {
public ListNode removeNthFromEnd (ListNode head, int n) {
// 定义虚拟头节点
ListNode newhead = new ListNode (-1, head);
// 定义栈
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode cur = newhead;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; i ++) {
stack.pop();
}
// stack.peek()检索到栈顶元素并获取到，但是不会被删除
ListNode prev = stack.peek();
prev.next = prev.next.next;
return newhead.next;
}
}
4.两两交换链表中的节点24中等
重点是要一直链起来，不要忽略某个步骤断掉链表
class Solution {
public ListNode swapPairs(ListNode head) {
// 定义一个虚拟头节点
ListNode newhead = new ListNode(-1, head);
// 一个节点一个节点进行遍历
ListNode cur = newhead;
while (cur.next != null && cur.next.next != null) {
ListNode bef = cur.next;
ListNode aft = cur.next.next;
// 交换
cur.next = aft; // 链住
bef.next = aft.next; // 交换
aft.next = bef;
cur = bef;
}
return newhead.next;
}
}
5.相交链表160简单
// class Solution {
// public:
// ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// // 使用哈希表存储节点。首先遍历链表A，将A中的节点存入哈希表，遍历链表B，如果B中的节点在哈希表中，之后的所有节点都要在hash表中；如果不在，继续遍历B的下一个节点
// // 定义以节点为元素的hash表
// unordered_set<ListNode *> visited;
// ListNode *temp = headA;
// while (temp != nullptr) {
// visited.insert(temp);
// temp = temp -> next;
// }
// temp = headB;
// while (temp != nullptr) {
// if (visited.count(temp)) {
// return temp;
// }
// temp = temp -> next;
// }
// return nullptr;
// }
// };
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 双指针，利用相遇的时候两个指针应该走过一样的步数
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA;
ListNode *pB = headB;
while (pA != pB) {
if (pA == nullptr) {
pA = headB;
} else {
pA = pA->next;
}
if (pB == nullptr) {
pB = headA;
} else {
pB = pB->next;
}
}
return pB;
}
};
【未完待续……】
总结：
如果由遍历且修改的需求，虚拟头接带你好使
链表要链起来始终
找规律，有没有简单实现的方法，例如反转链表，是不是头插法就很合适
思想：双指针！排序的话归并！
