LeetCode
206. 反转链表
反转一个单链表。
思路：
见注释。
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {// 第 1 步：先把 next 存起来，下一轮迭代要用到ListNode next = cur.next;// 第 2 步：实现当前节点的 next 指针的反转cur.next = pre;// 第 3 步：重新定义下一轮迭代的循环变量pre = cur;cur = next;}// 遍历完成以后，原来的最后一个节点就成为了 pre// 这个 pre 就是反转以后的新的链表的头指针return pre;}}
public class Solution {
public ListNode reverseList(ListNode head) {
// 特判
if (head == null || head.next == null) {
return head;
}
ListNode nextNode = head.next;
ListNode newHead = reverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
}
}
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
思路：
判断当前结点的值和下一结点的值是否相等，如果相等就跳过下一结点，否则将指针指向下一结点，继续循环。
执行用时：1 ms, 在所有 Java 提交中击败了72.24%的用户。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode newhead = head;
while (newhead != null && newhead.next != null) {
if (newhead.val == newhead.next.val) {
newhead.next= newhead.next.next;
} else {
newhead = newhead.next;
}
}
return head;
}
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return (head.val == head.next.val) ? head.next : head;
}
}
86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的结点都在大于或等于 x 的结点之前。
你应当保留两个分区中每个结点的初始相对位置。
思路：
其实就是把结点值小于 x 的挪到 x 之前。使用两个虚拟头结点，最后拼在一起。
执行用时：1 ms, 在所有 Java 提交中击败了23.89%的用户。（待优化）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode dummyL = new ListNode(-1);
ListNode dummyR = new ListNode(-1);
ListNode curL = dummyL, curR = dummyR;
int val;
while (head != null) {
val = head.val;
if (val < x) {
curL.next = head;
curL = curL.next;
} else {
curR.next = head;
curR = curR.next;
}
head = head.next;
}
curL.next = dummyR.next;
curR.next = null;
return dummyL.next;
}
}
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个结点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
思路：
在 l1 和 l2 有一者不为空的情况下进行循环，累加和放到 temp 中，新链表 p 指向 temp 对10取余的结果。重新定义下一轮迭代的循环变量，将 p 指向下一结点，temp 对10整除。注意 temp != 0 是为了最高位出现进位的情况。
执行用时：2 ms, 在所有 Java 提交中击败了99.86%的用户。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int temp = 0;
ListNode head = new ListNode(-1), p = head;
while (l1 != null || l2 != null || temp != 0) {
if (l1 != null) {
temp += l1.val;
l1 = l1.next;
}
if (l2 != null) {
temp += l2.val;
l2 = l2.next;
}
p.next = new ListNode(temp % 10);
p = p.next;
temp /= 10;
}
return head.next;
}
}
练习：
25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
思路：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null || k == 1) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, cur = head, next = null;
while(cur != null) {
// next指向第k个节点的下一个
int n = k;
next = cur;
while (next != null && n > 0) {
next = next.next;
--n;
}
// in case next group have less than k nodes
if (n > 0) {
pre.next = cur;
break;
}
// current k group: [cur, next)
// reverse the group and append the new head to the pre
pre.next = reverse(cur, next);
// update pre to be the first node of current k nodes group before reversing
pre = cur;
// update cur to be the next
cur = next;
}
return dummy.next;
}
private ListNode reverse(ListNode start, ListNode end) {
ListNode pre = null, temp = null;
while(start != end) {
temp = start.next;
start.next = pre;
pre = start;
start = temp;
}
return pre;
}
}
92. 反转链表 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1), pre = dummy;
dummy.next = head;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = m; i < n; i++) {
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = pre.next;
pre.next = temp;
}
return dummy.next;
}
}
160. 相交链表
328. 奇偶链表
445. 两数相加 II
剑指 Offer
剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
思路：
①顺序遍历，逆序存储。
利用ArrayList。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int len = list.size();
int[] res = new int[len];
for (int i = len - 1; i >= 0; i--) {
res[i] = list.get(len - i - 1);
}
return res;
}
}
利用栈。
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode temp = head;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
int size = stack.size();
int[] res = new int[size];
for (int i = 0; i < size; i++) {
res[i] = stack.pop().val;
}
return res;
}
}
②递归。
class Solution {
public int[] reversePrint(ListNode head) {
int cout = length(head);
int[] res = new int[cout];
reversePrintHelper(head, res, cout - 1);
return res;
}
//计算链表的长度
public int length(ListNode head) {
int cout = 0;
ListNode dummy = head;
while (dummy != null) {
cout++;
dummy = dummy.next;
}
return cout;
}
public void reversePrintHelper(ListNode head, int[] res, int index) {
if (head == null)
return;
reversePrintHelper(head.next, res, index - 1);
res[index] = head.val;
}
}
剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
思路：
链表。画图，构建pre、cur、next。先暂存cur.next到next中，然后将cur的next指向pre，pre指向cur，cur再指向next，进行下一轮循环，直到cur为null。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
思路：
链表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newHead = new ListNode(-1);
ListNode dummy = newHead;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
newHead.next = l2;
l2 = l2.next;
newHead = newHead.next;
} else {
newHead.next = l1;
l1 = l1.next;
newHead = newHead.next;
}
}
if (l1 != null) {
newHead.next = l1;
}
if (l2 != null) {
newHead.next = l2;
}
return dummy.next;
}
}
剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
思路：
链表，双指针。用环的思想来做，我们让两条链表分别从各自的开头开始往后遍历。当其中一条遍历到末尾时，我们跳到另一个条链表的开头继续遍历。两个指针最终会相等，而且只有两种情况。一种情况是在交点处相遇，另一种情况是在各自的末尾的空节点处相等。为什么一定会相等呢，因为两个指针走过的路程相同，是两个链表的长度之和，所以一定会相等。
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：42.8 MB, 在所有 Java 提交中击败了100.00%的用户
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode newA = headA, newB = headB;
while(newA != newB) {
if(newA == null) {
newA = headB;
} else {
newA = newA.next;
}
if(newB == null){
newB = headA;
} else {
newB = newB.next;
}
}
return newA;
}
}
若有收获，就点个赞吧
0 人点赞
