LeetCode——链表

LeetCode——链表

目录

  1. 概述
  2. 找出两个链表的交点
  3. 链表反转
  4. 归并两个有序的链表
  5. 从有序链表中删除重复节点
  6. 删除链表的倒数第n个节点
  7. 交换链表中的相邻节点
  8. 链表求和
  9. 回文链表
  10. 分隔链表
  11. 链表元素按奇偶聚集

0. 概述

  1. 链表是空节点，或者有一个值和一个指向下一个链表的指针，因此很多链表问题可以用递归来处理

1. 找出两个链表的交点

  1. 概述
    在这里插入图片描述
    1. A和B两个链表相交于c1，但不会出现相交后又分开的情况，因为每个节点只有一个next指针，也就只能有一个后继节点
2. 思路
  1. 设A的长度为a+c，B的长度为b+c，其中c为尾部公共部分长度，可知a+c+b = b+c+a
  2. 当访问A链表的指针访问到链表尾部时，令它从链表B的头部开始访问链表B；同样的，当访问链表B的指针访问到链表尾部时，令它从链表A的头部开始访问链表A。这样就能控制A和B两个链表的指针能同时访问到交点
  3. 如果不存在交点那么a+b=b+a，l1和l2同时为null，从而退出循环
3. 代码
public static ListNode getIntersectionNodeListNode head1, ListNode head2) {ListNode l1 = head1;ListNode l2 = head2;while l1 != l2) {l1 = l1 == null ? head2 : l1.next;l2 = l2 == null ? head1 : l2.next;}return l1;}
4. 补充
  1. 如果只是判断是否存在交点，那么有两种解法
    1. 把第一个链表的结尾连接到第二链表的开头，看第二链表是否存在环
    2. 或者直接比较两个链表的最后一个节点是否相同

2. 链表反转

1. 递归版
  1. 思路
    1. 设头节点为head，下一个节点为next。
    2. 通过递归reverseListnext)，所以可以到倒数第二个节点head和尾结点next。
    3. 将next.next指向前一个节点head，然后再将head.next置为null。从后到前依次反转
  2. 代码
2. 头插法
  1. 思路
    还不太懂…
  2. 代码
public static ListNode reverseListListNode head) {if head == null || head.next == null) {return head;}ListNode next = head.next;ListNode newHead = reverseListnext);next.next = head;head.next = null;return newHead;}public static ListNode reverseList2ListNode head) {ListNode newHead = new ListNode-1);while head != null) {ListNode next = head.next;head.next = newHead.next;newHead.next = head;head = next;}return newHead.next;}

3. 归并两个有序的链表

  1. 思路
    1. 如果l1,或者l2一开始就是null，那么没有任何操作需要合并，所以我们只需要返回非空链表。
    2. 否则就要判断l1和l2哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。
    3. 如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止
  2. 代码
public static ListNode mergeTwoListsListNode l1, ListNode l2) {if l1 == null) {return l2;}if l2 == null) {return l1;}if l1.val < l2.val) {l1.next = mergeTwoListsl1.next, l2);return l1;} else {l2.next = mergeTwoListsl1, l2.next);return l2;}}

4. 从有序链表中删除重复节点

1. 概述

在这里插入图片描述

2. 思路
  1. 直接法
    1. 由于输入的列表已排序，因此我们可以通过将结点的值与它之后的节点值进行比较来确定它是否为重复节点。如果它是重复的，则改当前节点的next指针，以便它跳到下一个节点并直接指向下一个节点之后的结点
  2. 递归
    1. 递归，head.next = deleteDuplicateshead.next)，会将结点依次压入栈中，最后取出进行比较，如果相同，则返回后一个节点，否则返回当前节点
3. 代码
public static ListNode deleteDuplicatesListNode head){if head==null||head.next==null){return head;}head.next = deleteDuplicateshead.next);return head.val == head.next.val?head.next:head;}public static ListNode deleteDuplicates2ListNode head){ListNode current = head;while current!=null||current.next!=null){if current.val==current.next.val){current.next = current.next.next;}else {current = current.next;}}return head;}

5. 删除链表的倒数第n个节点

1. 概述

在这里插入图片描述

2. 思路
  1. 可以创建两个指针：快指针fast和慢指针slow，快指针先走n步，然后快慢指针一起走到fast到链表末尾。此时慢指针slow所在位置就是需要删除的前一个结点。
3. 代码
public static ListNode removeNthFromEndListNode head, int n) {ListNode fast = head;ListNode slow = head;while n-- > 0) {fast = fast.next;}if fast == null) {return head.next;}while fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return head;}

6. 交换链表中的相邻结点

1. 概述

在这里插入图片描述

2. 思路
  1. 迭代
    1. 创建node节点（用于记录最后结果），next指向head，创建变量pre=node（pre用于移动链表下标）
    2. 当pre.next!=null&&pre.next.next!=null时，创建l1为pre.next节点，l2为pre的next.next节点，记录节点next=l2.next。然后开始交换
    3. l1.next指向next，l2.next指向l1，pre.next指向l2。完成交换，移动pre位置到l1
    4. 最后返回node.next
  2. 递归
    1. 从链表的头节点head开始递归
    2. 每次递归都负责交换一对节点。由firstNode和secondNode表示要交换的两个节点
    3. 下一次递归则是传递下一对需要交换的节点。如链表还有节点，则继续递归
    4. 交换了两个节点以后，返回secondNode，因为它是交换后的新头
    5. 在所有节点交换完成后，我们返回交换后的头，实际就是原始链表的第二个节点
3. 代码
public static ListNode swapPairsListNode head) {ListNode node = new ListNode-1);node.next = head;ListNode pre = node;while pre.next != null && pre.next.next != null) {ListNode l1 = pre.next;ListNode l2 = pre.next.next;ListNode next = l2.next;l1.next = next;l2.next = l1;pre.next = l2;pre = l1;}return node.next;}public static ListNode swapPairs2ListNode head) {if head == null || head.next == null) {return head;}ListNode first = head;ListNode second = head.next;first.next = swapPairs2second.next);second.next = first;return second;}

7. 链表求和

1. 概述

在这里插入图片描述

2. 思路
  1. 创建两个栈保存两个链表的值，创建head头节点固定待会需要创建的链表的头节点，carry遍历则记录需要进位的数
  2. 当l1Stack或者l2Stack不为null，或者carry!=0（表示需要进位）时，进行while循环
  3. 当l1Stack不为null 则取出栈顶元素，否则为0，设为遍历x。当l1Stack不为null 则取出栈顶元素，否则为0，设为遍历y。sum为x+y+carry。
  4. 得出计算结果后创建新节点，节点值为sum%10，然后与头节点相连。node.next=head.next，head.next=node
  5. 最后记录carry需要进位值carry=sum/10
  6. 返回head.next
3. 代码
public static ListNode addTwoNumersListNode l1, ListNode l2) {Stack<Integer> l1Stack = bulidStackl1);Stack<Integer> l2Stack = bulidStackl2);ListNode head = new ListNode-1);int carry = 0;while !l1Stack.isEmpty) || !l2Stack.isEmpty) || carry != 0) {int x = l1Stack.isEmpty) ? 0 : l1Stack.pop);int y = l2Stack.isEmpty) ? 0 : l2Stack.pop);int sum = x + y + carry;ListNode node = new ListNodesum % 10);node.next = head.next;head.next = node;carry = sum / 10;}return head.next;}private static Stack<Integer> bulidStackListNode l) {Stack<Integer> stack = new Stack<>);while l != null) {stack.pushl.val);l = l.next;}return stack;}

8. 回文链表

1. 概述

LeetCode234
在这里插入图片描述

2. 思路

方法一：将值复制到数组中后用双指针法

  1. 复制链表值到数组列表中
  2. 利用双指针法判断是否为回文

方法二：快慢指针法（ On) 时间复杂度和 O1) 空间复杂度）

  1. 创建慢指针slow=head，快指针fast=head.next，当fast不为null或者fast.next不为null时，慢指针走一步，快指针走两步
  2. 如果fast!=null，即偶数节点，让slow执行下一个节点
  3. 然后进行切分，当head.next=slow时，退出while循环，否则head=head.next。断开前半部分链表，head.next=null
  4. 反转后半部分链表，然后进行比较值
3. 代码
public static boolean isPalindromeListNode head) {if head == null || head.next == null) {return true;}ListNode slow = head, fast = head.next;while fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}if fast != null) {slow = slow.next; // 偶数节点，让slow指向下一个节点}cuthead, slow); //切成两个链表return isEqualhead, reverseslow));}private static boolean isEqualListNode l1, ListNode l2) {while l1 != null && l2 != null) {if l1.val != l2.val)return false;l1 = l1.next;l2 = l2.next;}return true;}private static ListNode reverseListNode head) {if head == null || head.next == null) {return head;}ListNode next = head.next;ListNode newHead = reversenext);next.next = head;head.next = null;return newHead;}private static void cutListNode head, ListNode cutNode) {while head.next != cutNode) {head = head.next;}head.next = null;}public static boolean isPalindrome2ListNode head) {List<Integer> list = new ArrayList<>);while head != null) {list.addhead.val);head = head.next;}int l = 0;int r = list.size) - 1;while l < r) {if list.getl) != list.getr))) {return false;}l++;r--;}return true;}

9. 分隔链表

1. 概述
  1. 给定一个结点为root的链表，编写一个函数以将链表分隔为K个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不超过1，也就说可能有些部分为null，k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分长度应该大于或等于后面的长度
2. 思路
  1. 创建遍历N记录原始链表长度，用于计算每个分区的链表长度，size=N/k（每个分区的最少长度），mod=N%k（开始的分区还需要多的个数），如长度为10的链表分成三个分区，第一个分区多一个元素
  2. 创建链表数组，容量为k，当cur结点不为null，for循环对分区进行遍历
    1. 计算每个分区的链表长度curSize=size+mod– > 0?1:0)
    2. 计算出分区长度后，对cur结点进行后移
  3. 进行切分链表
    1. 记录cur的下一个节点为next
    2. 将cur.next = null
    3. cur = next
3. 代码
public static ListNode[] splitListToPartsListNode root, int k) {int N = 0;ListNode cur = root;while cur!=null){N++;cur = cur.next;}int mod = N%k;int n = N/k;ListNode[] ret = new ListNode[k];cur = root;for int i = 0;cur!=null&& i < k; i++) {ret[i] = cur;int curSize = n+mod-->0?1:0);for int j = 0; j < curSize - 1; j++) {cur = cur.next;}ListNode next = cur.next;cur.next = null;cur = next;}return ret;}

10. 链表元素按奇偶聚集

1. 概述
  1. 给定一个链表，把所有的奇数节点和偶数节点分别排在一起。这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性（LeetCode328）
2. 思路
  1. 一个LinkedList需要一个头指针和一个尾指针来支持双端操作
  2. 用变量head和odd保存奇链表的头和尾指针。evenHead和even保存偶链表的头和尾指针。算法会遍历原链表一次并把奇节点放到奇链表里去、偶节点放到偶链表里去。
  3. 遍历整个链表还需要一个指针作为迭代器。这里odd和even指针不仅仅是尾指针，也可以扮演原链表的迭代器角色
3. 代码
public static ListNode oddEvenListListNode head) {if head == null) {return head;}ListNode odd = head, even = head.next, evenHead = even;while even != null && even.next != null) {odd.next = odd.next.next;odd = odd.next;even.next = even.next.next;even = even.next;}odd.next = evenHead;return head;}

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注