从尾到头打印链表
栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
ListNode temp = head;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
int size = stack.size();
int[] print = new int[size];
for (int i = 0; i < size; i++) {
print[i] = stack.pop().val;
}
return print;
}
反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* a=nullptr;
ListNode* b=head;
while(b!=nullptr){
ListNode* temp = b->next; // 拿到下一个
b->next = a; // 将当前反转
a=b; // 获取上一个指针
b=temp; // 获取下一个指针
}
return a;
}
};
递归
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
删除链表的节点
class Solution {
//双指针
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val){
return head.next;
}
ListNode cur = head;
ListNode se = cur.next ;
while(se != null){
if(se.val == val){
cur.next = se.next;
se = null;
break;
}
cur = se;
se = se.next;
}
return head;
}
//单指针
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val){
return head.next;
}
ListNode cur = head;
while(cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
break;
}
cur = cur.next;
}
return head;
}
}
链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
双指针，前面的指针先走k步，然后两个指针一起走，知道走到最后，两个指针之间的位置就是
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head;
for(int i = 0; i < k; i++)
former = former.next;
while(former != null) {
former = former.next;
latter = latter.next;
}
return latter;
}
合并两个排序的链表
双指针遍历两个链表，进行比较，小的放入新的链表中，直到两个链表都遍历完毕
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0), cur = dum;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dum.next;
}
两个链表的第一个公共节点
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
大家的题解都是双指针双百解法。
我来说一个这题的实际应用：
求两个类最低一层的公共父类，就是两个树节点最低一层的公共祖先节点。
这里的树节点内容不是left和right，而是指向父节点的指针。
两个类都用.getSuperclass()方法生成直到Object的两个链表，
再调用这个题的方法就求出了第一个公共祖先。
我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA, b = headB;
int len1 = 0, len2 = 0, sum = 0;
while(a != null && ++len1 > 0) a = a.next;
while(b != null && ++len2 > 0) b = b.next;
a = headA;
b = headB;
while (a != b){
if(a.next == null) a = headB;
else a = a.next;
if(b.next == null) b = headA;
else b = b.next;
if(sum++ > len1 + len2) return null;
}
return a;
}
}
复杂链表的复制
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>(); //创建HashMap集合
Node cur=head;
//复制结点值
while(cur!=null){
//存储put:<key,value1>
map.put(cur,new Node(cur.val)); //顺序遍历，存储老结点和新结点(先存储新创建的结点值)
cur=cur.next;
}
//复制结点指向
cur = head;
while(cur!=null){
//得到get:<key>.value2,3
map.get(cur).next = map.get(cur.next); //新结点next指向同旧结点的next指向
map.get(cur).random = map.get(cur.random); //新结点random指向同旧结点的random指向
cur = cur.next;
}
//返回复制的链表
return map.get(head);
}
设计链表
getIndex
addHead
addLast
addAtIndex
deleteIndex
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class MyLinkedList {
int size;
ListNode head; // sentinel node as pseudo-head
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
// if index is invalid
if (index < 0 || index >= size) return -1;
ListNode curr = head;
// index steps needed
// to move from sentinel node to wanted index
for(int i = 0; i < index + 1; ++i) curr = curr.next;
return curr.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
addAtIndex(0, val);
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
addAtIndex(size, val);
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
// If index is greater than the length,
// the node will not be inserted.
if (index > size) return;
// [so weird] If index is negative,
// the node will be inserted at the head of the list.
if (index < 0) index = 0;
++size;
// find predecessor of the node to be added
ListNode pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
// node to be added
ListNode toAdd = new ListNode(val);
// insertion itself
toAdd.next = pred.next;
pred.next = toAdd;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
// if the index is invalid, do nothing
if (index < 0 || index >= size) return;
size--;
// find predecessor of the node to be deleted
ListNode pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
// delete pred.next
pred.next = pred.next.next;
}
}
链表相交
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode t1 = headA;
ListNode t2 = headB;
while(t1 != t2){
t1 = t1 != null ? t1.next : headB;
t2 = t2 != null ? t2.next : headA;
}
return t2;
}
}
环形链表
方法一：哈希表
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
方法二：双指针
通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
链表求和
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//初始进位为0
int pre = 0;
//操作数
ListNode mid = new ListNode(0);
//返回头节点
ListNode anws = mid ;
//当l1和l2都不为null时进入while循环
while(l1!=null&&l2!=null){
//操作数赋值
mid.val = (l1.val+l2.val+pre)%10;
//更新进位
pre = (l1.val+l2.val+pre)/10;
//更新头节点
l1 = l1.next;
l2=l2.next;
//头节点更新后判断是否为空
if(l1==null){
//如果l1头节点为空且进位为0，则操作数的next直接为l2剩下的
if(pre==0) {
mid.next = l2;
return anws;
}else {
//如果有进位，则递归调用addTwoNumbers方法
mid.next = addTwoNumbers(l2,new ListNode(pre));
return anws;
}
}
//同上
if(l2 == null){
if(pre==0) {
mid.next = l1;
return anws;
}else {
mid.next = addTwoNumbers(l1,new ListNode(pre));
return anws;
}
}
//l1 l2更新后都不为null，则设置操作数为0 进入下一次while循环
mid.next =new ListNode(0);
mid = mid.next;
}
//l1为null，直接不能进入上面while循环的情况下，直接返回l2
if(l1==null){
return l2;
}//同上
else if(l2 ==null){
return l1;
}
return anws;
}
}
回文链表
1，采用快慢两个指针去寻找链表的中间节点；
2，根据链表的中间节点反转后一半的链表；
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
ListNode midNode = findMidNode(head);
ListNode secondHalfHead = reverseLinked(midNode.next);
ListNode curr1 = head;
ListNode curr2 = secondHalfHead;
boolean palindrome = true;
while(palindrome && curr2 != null){
if(curr1.val != curr2.val) palindrome = false;
curr1 = curr1.next;
curr2 = curr2.next;
}
return palindrome;
}
/* 反转链表 */
private ListNode reverseLinked(ListNode head){
ListNode cur = head;
ListNode prev = null;
while(cur != null){
ListNode nextTemp = cur.next;
cur.next = prev;
prev = cur;
cur = nextTemp;
}
return prev;
}
/* 快慢指针寻找中间节点 */
private ListNode findMidNode(ListNode head){
ListNode fast = head;
ListNode low = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
low = low.next;
}
return low;
}
}
旋转链表
先将链表闭合成环
找到相应的位置断开这个环，确定新的链表头和链表尾
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// base cases
if (head == null) return null;
if (head.next == null) return head;
// close the linked list into the ring
ListNode old_tail = head;
int n;
for(n = 1; old_tail.next != null; n++)
old_tail = old_tail.next;
old_tail.next = head;
// find new tail : (n - k % n - 1)th node
// and new head : (n - k % n)th node
ListNode new_tail = head;
for (int i = 0; i < n - k % n - 1; i++)
new_tail = new_tail.next;
ListNode new_head = new_tail.next;
// break the ring
new_tail.next = null;
return new_head;
}
}
排序链表
归并排序（递归法）
解答一：归并排序（递归法）
分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
}
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起
将奇节点放在一个链表里，偶链表放在另一个链表里。然后把偶链表接在奇链表的尾部。
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
链表的中间结点
方法一：数组
class Solution {
public ListNode middleNode(ListNode head) {
ListNode[] A = new ListNode[100];
int t = 0;
while (head != null) {
A[t++] = head;
head = head.next;
}
return A[t / 2];
}
}
方法二：单指针法
我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。
class Solution {
public ListNode middleNode(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
++n;
cur = cur.next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur.next;
}
return cur;
}
}
方法三：快慢指针法
slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
K个一组翻转链表
主要考虑翻转后如何链接
const myReverse = (head, tail) => {
let prev = tail.next;
let p = head;
while (prev !== tail) {
const nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return [tail, head];
}
var reverseKGroup = function(head, k) {
const hair = new ListNode(0);
hair.next = head;
let pre = hair;
while (head) {
let tail = pre;
// 查看剩余部分长度是否大于等于 k
for (let i = 0; i < k; ++i) {
tail = tail.next;
if (!tail) {
return hair.next;
}
}
const nex = tail.next;
[head, tail] = myReverse(head, tail);
// 把子链表重新接回原链表
pre.next = head;
tail.next = nex;
pre = tail;
head = tail.next;
}
return hair.next;
};