目录

第一题：从尾到头打印链表

第二题：删除链表的节点

第三题：链表中倒数第k个节点

第四题：反转链表

第五题：合并两个排序的链表

第六题：两个链表的第一个公共节点

第一题：从尾到头打印链表

 官方答案：栈

class Solution {public int[] reversePrint(ListNode head) {Stack stack = new Stack();//定义⼀个栈，栈内元素后进先出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 {ArrayList tmp = new ArrayList();//创建新的数组链表public int[] reversePrint(ListNode head) {recur(head);//倒转链表int[] res = new int[tmp.size()];//创建新数组for(int i = 0; i < res.length; i++)res[i] = tmp.get(i);//把数组链表temp转化为数组resreturn res;}void recur(ListNode head) {//递归体if(head == null) return;recur(head.next);//递归⼊⼝，层层递归，递归没有结束时，下⾯这句语句是⽆法执⾏的tmp.add(head.val);//递归结束了，开始层层回溯，把当前节点值加⼊列表//上⾯的递归和回溯过程总体上看，就像⼀个U型滑板场}
}
//我写题时，就是来到单链表尾部后就不知道怎么回去了

简化后的递归：

class Solution {int[] res;int i = 0;int j = 0;public int[] reversePrint(ListNode head) {solve(head);return res;}public void solve(ListNode head){//递归体if(head == null){res = new int[i];return;}i++;solve(head.next);res[j] = head.val;j++;}
}

第二题：删除链表的节点

 网友答案：双指针

class Solution {public ListNode deleteNode(ListNode head, int val) {if(head.val == val) return head.next;//要删除的是头节点，就直接返回头节点的下⼀个节点就⾏了ListNode pre = head, cur = head.next;//定义两个指针，cur表示当前节点，它将指向要删除的节点，pre指向当前节点的前⼀个节点while(cur != null && cur.val != val) {pre = cur;cur = cur.next;//两个指针都往后移⼀步，cur和pre始终处于前后位置}if(cur != null) pre.next = cur.next;//pre.next原本应该是curreturn head;}
}

网友答案：单指针

class Solution {public ListNode deleteNode(ListNode head, intval) {if (head == null) return null;if (head.val == val) return head.next;ListNode cur = head;while (cur.next != null && cur.next.val !=val)//注意这⾥是cur.next.val，如果是cur.val==val,即cur为要删除的节点，//但再往回⼀步，来到前节点改变它的后指向很麻烦，所以直接判断当前节点的下⼀个节点的值cur = cur.next;if (cur.next != null)cur.next = cur.next.next;return head;}
}//我写题时，主要问题是，我⽤head当成指针往后⾛，删掉元素后，head 回不到头部，直接返回head，得到的结果不完整。所以，应该⽤⼀个新指针来遍历链表

网友答案：递归

class Solution {public ListNode deleteNode(ListNode head, int val) {if (head == null) {return null;}if (head.val == val) {return head.next;} else {head.next = deleteNode(head.next, val);}return head;}
}
//空间复杂度为O(n)，效率⽐双指针低

第三题：链表中倒数第k个节点

 官方答案：

法一：顺序法

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {int n = 0;ListNode node = null;for (node = head; node != null; node = node.next) {n++;}for (node = head; n > k; n--) {node = node.next;}return node;}
}
//思路和我的⼀样，但代码整体上⽐我的要集中⼀点，我的写得有点散

法二：快慢指针

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode fast = head;//快指针ListNode slow = head;//慢指针while (fast != null && k > 0) {//当快指针⾛了k步时，慢指针才出发，它们之间的步数差永远为kfast = fast.next;k--;}while (fast != null) {//当快指针⾛到尽头时，慢指针刚好在它前k个位置fast = fast.next;slow = slow.next;}return slow;}
}

网友答案：栈

class Solution {public ListNode getKthFromEnd(ListNode head, int k) {Deque d = new ArrayDeque<>();while (head != null) {//将所有节点都压⼊栈中d.addLast(head);head = head.next;}ListNode ans = null;while (k-- > 0) ans = d.pollLast();//从栈顶弹出k个元素，最后⼀个出栈的元素即为所求return ans;}
}

第四题：反转链表

 官方答案：

法一：

class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;//原链表的第⼀个节点反//转后必须指向空，否则链表中可能会产⽣环，因为此节点原来就//是指向第⼆个节点的，如果不改变它的指向，反转链表后，它还//是指向第⼆个节点ListNode curr = head;while (curr != null) {ListNode next = curr.next;//存储节点，此时尚未引⽤，防⽌被覆盖curr.next = prev;//把当前节点的next指针改为指向前⼀个节点prev = curr;//节点都往后移⼀位curr = next;}return prev;//返回头引⽤}
}

法二：递归

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {//递归到尽头的条件return head;}ListNode newHead =reverseList(head.next);//层层递进，head最终来到链表的//尾部，链表最后⼀个节点成为新的头引⽤head.next.next = head;head.next = null;//head.next = null; 网友理解的是每次反转完成之后就把尾巴上的指                        //针翘起来指向天空，等着后面的大哥接上。 head.next.next = head;这句 //话只是把翘起来的指针插自己身上了。完事之后，自己也翘起来 head.next = null;return newHead;//层层回溯时，返回的是不断往前缩短的链表的最后⼀个元素}
}

网友答案：

class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head, pre = null;while(cur != null) {ListNode tmp = cur.next; // 暂存后继节点cur.nextcur.next = pre; // 修改 next 引⽤指向pre = cur; // pre 暂存 curcur = tmp; // cur 访问下⼀节点}return pre;}
}

网友答案：

class Solution {public ListNode reverseList(ListNode head) {return recur(head, null); // 调⽤递归并返回}private ListNode recur(ListNode cur, ListNode pre) {if (cur == null) return pre; // 终⽌条件ListNode res = recur(cur.next, cur); // 递归后继节点cur.next = pre; // 修改节点引⽤指向return res; // 返回反转链表的头节点}
}

第五题：合并两个排序的链表

 官方答案：

法一：递归

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

法二：双指针

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode prehead = new ListNode(-1);//设定⼀个哨兵节点preheadListNode prev = prehead;//维护⼀个prev指针，不断地往后移，调整next指针是指向l1还是l2while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;//l1表示链表1的当前节点，prev.next=l1表示把链表1的当前节点接⼊前⾯的合并链表l1 = l1.next;//l1指针往后移⼀位} else {prev.next = l2;l2 = l2.next;}prev = prev.next;//⽆论prev指针指向l1还是l2，它都要往后移一位}
// 合并后 l1 和 l2 最多只有⼀个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 == null ? l2 : l1;//l1和l2肯定⾄少有⼀个为空了return prehead.next;}
}

第六题：两个链表的第一个公共节点

 看不懂题目，觉得输入里不是已经包括答案了吗？还写什么？

 官方答案：

法一：哈希集合

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set visited = new HashSet();//新建一个哈希集合ListNode temp = headA;//指针temp指向链表Awhile (temp != null) {visited.add(temp);//把链表A的每个节点都加入哈希集合temp = temp.next;}temp = headB;//指针temp指向链表Bwhile (temp != null) {if (visited.contains(temp)) {//遍历链表B，判断是否和A有相同节点return temp;}temp = temp.next;}return null;//两个链表不相交}
}

法二：双指针

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {//两个指针是同步走的，无论两个链表的长度关系如何，//只要链表相交，那两个指针一定会同时到达第一个公共节点pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

 网友答案：枚举法

public class Solution {public ListNode getIntersectionNode(ListNode a, ListNode b) {for (ListNode h1 = a; h1 != null ; h1 = h1.next) {//双层for循环for (ListNode h2 = b; h2 != null ; h2 = h2.next) {if (h1 == h2) return h1;}}return null;}
}

网友答案：队列

public class Solution {public ListNode getIntersectionNode(ListNode a, ListNode b) {Deque d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();//栈是后进先出while (a != null) {//把链表a的所有节点压入栈d1.add(a);a = a.next;}while (b != null) {//把链表b的所有节点压入栈d2.add(b);b = b.next;}ListNode ans = null;while (!d1.isEmpty() && !d2.isEmpty() && d1.peekLast() == d2.peekLast()) {d1和d2都不为空时，循环比较栈顶元素ans = d1.pollLast();//记录上一位栈顶元素，一旦遇到第一个不同的节点，就结束循环d2.pollLast();}return ans;}
}

网友答案：Set

public class Solution {public ListNode getIntersectionNode(ListNode a, ListNode b) {Set set = new HashSet<>();while (a != null) {//记录链表a的所有节点set.add(a);a = a.next;}while (b != null && !set.contains(b)) b = b.next;//遍历链表b，检查当前节点是否在set中出现过，第一个出现过的节点即是交点return b;}
}