题目描述： 给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例： 输入：head = 1->4->3->2->5->2, x = 3 输出：1->2->2->4->3->5 解法： 只需要遍历链表的所有节点，小于x的放到一个小的链表中，大于等于x的放到一个大的链表中，最后再把这两个链表串起来即可。 代码 public ListNode partition(ListNode head, int x) { //小链表的头 ListNode smallHead = new ListNode(0); //大链表的头 ListNode bigHead = new ListNode(0); //小链表的尾 ListNode smallTail = smallHead; //大链表的尾 ListNode bigTail = bigHead; //遍历head链表 while (head != null) { i....
题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶： 你是否可以使用 O(1) 空间解决此题？ 解法： 1.哈希表 遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环 2.双指针 代码： 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) { fast = head; while(fast != slow) ....
题目描述 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 解法： 1. 递归解法： int cur = 0; public ListNode removeNthFromEnd(ListNode head, int n) { if (head == null) { return null; } head.next = removeNthFromEnd(head.next, n); cur++; if(n == cur) { return head.next; } return head; } 运行结果： 2. 快慢指针 利用快慢指针，快指针先走n不，然后快慢指针一起走，当快指针到链表尾部时，slow刚好到n-1的位置。删除slow.next 即可 public ListNode removeNthFromEnd(ListNode head, int n) { if (he....
题目描述： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 解法： 两个链表顺序遍历，对应两个节点的值相加作为新链表的值，如果产生进位，需要加到下一位。 sumVal / 10 等于1就是产生了进位，为0则没有进位 sumVal % 10则是新节点的值 构造root空节点，作为新链表的头节点（最终返回root.next节点） 构造游标节点的作用 ？ 为了标记处理新节点的当前位置 为什么不复用root节点新建了游标节点？这样做最终返回新节点时找不到头节点 Java代码如下： public ListNode addTwoNumbers(List....
题目描述： 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 解法： 利用归并排序，从中间节点断开，分别排序，排序时利用递归。再合并排序结果。 public ListNode sortList(ListNode head) { // 1、递归结束条件 if (head == null || head.next == null) { return head; } // 2、找到链表中间节点并断开链表 & 递归下探 ListNode midNode = middleNode(head); ListNode rightHead = midNode.next; midNode.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); // 3、当前层业务操作（合并有序链表） return mergeTwoList....
题目描述 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。 解法 public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } 运行结果：
题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 解法 迭代解法： public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode current = head; while(current != null) { ListNode next = current.next; current.next = pre; pre = current; current = next; } return pre; } 运行结果： 递归解法 head.next 之下的节点都已经反转好 head.next.next = head 节点 head.next 置为null public ListNode reverseList(ListNode head) { if (head == null || head.next ....
题目描述 编写一个程序，找到两个单链表相交的起始节点。 解法 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode nodeA = headA; ListNode nodeB = headB; while(nodeA != nodeB) { nodeA = nodeA == null ? headB : nodeA.next; nodeB = nodeB == null ? headA : nodeB.next; } return nodeA; } 运行结果：
题目描述 给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。 解法 经典解法、快慢指针 public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { hasCycle = true; break; } } return hasCycle; } 运行结果：
题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 解法 递归 解法如下： public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 递归 if (l1 == null) { return l2; } if(l2 == null) { return l1; } if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } 运行结果： 迭代 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new L....