1.链表（一）
2020-08-06 本文已影响0人
今天柚稚了么
题目汇总https://leetcode-cn.com/tag/linked-list/
2. 两数相加中等
19. 删除链表的倒数第N个节点中等 [✔]
21. 合并两个有序链表简单 [✔]
23. 合并K个排序链表困难(没有做)
24. 两两交换链表中的节点中等[✔]
25. K 个一组翻转链表困难(没有做)
61. 旋转链表中等
82. 删除排序链表中的重复元素 II中等
83. 删除排序链表中的重复元素简单[✔]
86. 分隔链表中等[✔]
2. 两数相加中等
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1!=null || l2!=null){
int i = (l1 != null) ? l1.val : 0;
int j = (l2 != null) ? l2.val : 0;
int sum = i + j + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1!=null)
l1 = l1.next;
if(l2!=null)
l2 = l2.next;
}
if(carry==1)
cur.next = new ListNode(carry);
return pre.next;
}
}
19. 删除链表的倒数第N个节点中等 [✔]
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
思路一：两次遍历
删除链表的倒数第N个结点相当于删除链表的第(L-N+1)个结点。第一次遍历得出链表的长度L，哑结点的设置非常有必要。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = head;
int length = 0;
while(first!=null){
first = first.next;
length++;
}
length = length - n;
first = dummy;
while(length>0){
first = first.next;
length--;
}
first.next = first.next.next;
return dummy.next;
}
}
思路二：一次遍历
使用两个指针，两个指针之间保持恒定的间隔，当第一个指针到达最后一个结点时，第二个指针将指向从最后一个结点数起的第 n 个结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//设置哑结点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = head;
ListNode second = head;
//第一个指针先指向第(l-n+2)个结点，即要删除的结点的前一个结点
for(int i=1;i<=n+1;i++){
first = first.next;
}
//两个指针一起移动，第二个指针指向要删除的结点
while(first!=null){
first = first.next;
second = second.next;
}
//此时删除结点
second.next = second.next.next;
return dummy.next;
}
}
21. 合并两个有序链表简单 [✔]
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路：直接归并排序
/**
* 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 dummy = new ListNode(-1);
ListNode cur = dummy;
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;
}
//一个链表为空
if(l1==null){
cur.next = l2;
}
else if(l2==null){
cur.next = l1;
}
return dummy.next;
}
}
思路二：递归
两个链表头部较小的一个与剩下元素的 merge 操作结果合并
/**
* 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) {
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;
}
}
}
23. 合并K个排序链表困难
合并 k个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
24. 两两交换链表中的节点中等[✔]
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定1->2->3->4, 你应该返回2->1->4->3.
思路一：非递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
pre.next = head;
while(pre.next!=null&&pre.next.next!=null){
ListNode t = pre.next.next;
pre.next.next = t.next;
t.next = pre.next;
pre.next = t;
pre = t.next;
}
return dummy.next;
}
}
思路二：递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode first = head;
ListNode second = head.next;
head = second;
first.next = swapPairs(second.next);
second.next = first;
return head;
}
}
25. K 个一组翻转链表困难
给你一个链表，每 k个节点一组进行翻转，请你返回翻转后的链表。
k是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k的整数倍，那么请将最后剩余的节点保持原有顺序。
给你这个链表：1->2->3->4->5
当 k= 2 时，应当返回:2->1->4->3->5
当 k= 3 时，应当返回:3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
61. 旋转链表中等
给定一个链表，旋转链表，将链表每个节点向右移动 k个位置，其中 k是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
思路：
找到链表的表尾，表尾指向表头，将链表闭合成环，再确定新的链表头和链表尾
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return null;
if (head.next == null)
return head;
ListNode cur = head;
int length = 1;
while(cur.next!=null){
length++;
cur = cur.next;
}
cur.next = head;//链表连成环
for(int i=0;i<length-k%length;i++){
cur = cur.next;
}
ListNode new_head = cur.next;//找到新的链表头
cur.next = null;//断开
return new_head;
}
}
82. 删除排序链表中的重复元素 II中等
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
输入: 1->2->3->3->4->4->5
输出: 1->2->5
思路：
创建一个临时指针temp
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while(cur.next!=null&&cur.next.next!=null){
ListNode temp = cur.next;
if(cur.next.val == cur.next.next.val){
while (temp != null && temp.next != null && temp.val == temp.next.val ) {
temp = temp.next;
}
cur.next = temp.next;
}
else
cur = cur.next;
}
return dummy.next;
}
}
83. 删除排序链表中的重复元素简单[✔]
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2
输出: 1->2
思路：
比较当前结点的值和它之后的结点值确定它是否为重复结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
86. 分隔链表中等[✔]
给定一个链表和一个特定值x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路：双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户，2020/08/06
public ListNode partition(ListNode head, int x) {
ListNode beforeHead = new ListNode(0);
ListNode before = beforeHead;
ListNode afterHead = new ListNode(0);
ListNode after = afterHead;
while(head != null){
if(head.val < x){
before.next = head;
before = before.next;
}else{
after.next = head;
after = after.next;
}
head = head.next;
}
before.next = afterHead.next;
after.next = null;
return beforeHead.next;
}
}
