leetcode链表相关

时间:2024-08-30 15:34:20

2/445两数相加

2两数相加(链表倒排结果)

思路:

  • 设置dummy,结果指针p
  • 遍历,只要其中一个没有遍历完就继续;
    • 如果l1不为空,加到sum,l1移到下一位
    • 如果l2不为空,加到sum,l2移到下一位
    • p指向新节点(sum % 10),p移到下一位
    • sum /= 10
  • 判断最后一个节点是否需要进1
  • 返回dummy.next

445两数相加 II(链表顺排结果)

思路:

  • 2两数相加 + leetcode 206反转链表:reverse l1和l2,然后执行两数相加,最后结果再反转

    另一个思路:把l1和l2的值分别放进两个stack,在相加时,指针p值设为sum % 10,然后新建节点(sum / 10)指向res,然后res成为该新节点。最终要检查res值是否为0,如果是就返回res.next

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    // ListNode reversedList1 = reverse(l1);
// ListNode reversedList2 = reverse(l2);
// 固定头部,设置指针、sum
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int sum = 0; // 遍历,只要其中一个没有遍历完就继续
while (l1 != null || l2 != null){
// 如果l1不为空,加到sum
if (l1 != null){
sum += l1.val;
l1 = l1.next;
} // 如果l2不为空,加到sum
if (l2 != null){
sum += l2.val;
l2 = l2.next;
} // 创建next节点,并移动指针
p.next = new ListNode(sum % 10);
p = p.next; // 更新sum
sum /= 10;
} // 判断最后一个节点是否需要进1
if (sum == 1){
p.next = new ListNode(1);
} // 返回头部
return dummy.next;
// return reverse(dummyHead.next);
}

综合题(328奇偶链表, 206反转链表, 21合并两个有序链表 )

奇数节点递增,偶数节点递减。将这个链表变为升序链表。

比如:1 8 3 6 5 4 7 2 9,最后输出1 2 3 4 5 6 7 8 9。

思路:

  1. 分开奇偶节点(328奇偶链表)
  2. 反转偶节点组成的链表(206反转链表)
  3. 合并链表(21合并两个有序链表)

1和2可以合并,即在分开偶节点同时对其进行反转,下面代码便是基于此实现的。不好描述,按照代码画图就可以理解了。

public static ListNode oddEvenListAndReverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head; ListNode op = head, ep = head.next, epre = null;
// 在不反转,且需要把奇链表和偶链表连在一起时,需要一个变量固定偶节点的开头
// eHead = ep;
while (ep != null && ep.next != null) {
op = op.next = ep.next;
// 下面为分开偶节点 + 反转
ep.next = epre;
epre = ep;
ep = op.next;
// 下面是单纯分开偶节点
// ep = ep.next = op.next;
} // 整理出ol和el
ListNode ol = dummy.next;
// 决定el的头节点是epre还是ep
ListNode el;
if (ep == null){
el = epre;
}else {
ep.next = epre;
el = ep;
} // 合并链表
ListNode p = dummy;
while ( ol != null && el != null) {
if (el.val < ol.val){
p.next = el;
el = el.next;
}else {
p.next = ol;
ol = ol.next;
}
p = p.next;
} p.next = (ol != null) ? ol : el; return dummy.next;
}

92反转链表 II

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路:

  • 与全反转不同,需要dummy,因为不确定head是否需要反转。
  • 新建cur试探指针,从dummy开始,移动到要反转的节点的前一个节点的位置。
  • 与全反一样,需要front指针。另外需要pre和last。前者用来接上之后反转部分的头部,所以它等于当前的cur;后者为reverse部分的结尾部,即当前cur.next,用于最后连接剩余部分
  • 遍历,cur开始试探(cur = pre.next),pre指向cur的下一位(记住剩余部分的头部),然后就是全反中的cur指向front,然后front成为cur。
  • cur移到剩余部分的头部,此时pre就可以指向反转部分的头部front,last指向剩余部分cur
// 注意本题m代表第m个node
ListNode dummy = new ListNode(-1);
dummy.next = head; ListNode cur = dummy;
// 在要reverse的那个节点的前一个节点停下
for (int i = 1; i < m; i++) {
cur = cur.next;
} // front 是 reverse 部分的头部,紧跟cur,但循环结束后并不跟cur走出 reverse 部分
ListNode front = null;
// pre 用于固定前部分的最后一个节点的位置,它不断指向cur的下一个节点
ListNode pre = cur;
// last 用于固定 reverse 部分的结尾,最后用于连接剩余部分
ListNode last = cur.next; // 对n - m + 1个节点做修改,所以要包含n
for (int i = m; i <= n; i++) {
// cur 接触到的都是要修改指向的
// cur从 2 走到 4
cur = pre.next;
pre.next = cur.next;
cur.next = front;
front = cur;
} // cur 走到 5
cur = pre.next;
// pre 指向 4
pre.next = front;
// last 指向 5
last.next = cur;
return dummy.next;

链表排序(148排序链表, 876链表的中间结点)

链表排序:148排序链表、876链表的中间结点(结合141环形链表、142环形链表 II)、21合并两个有序链表 、23合并k个排序链表

思路:

  1. 找中间节点(876链表的中间结点),然后断开
  2. 对分开的两个链表递归调用链表排序函数,这两个函数作为merge(21合并两个有序链表)的参数
// null情况
if (head == null || head.next == null) return head; // 快慢指针拆分
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
} // 断开关联
ListNode tmp = slow;
slow = slow.next;
tmp.next = null; // 递归调用
return merge(sortList(head), sortList(slow));

142环形链表 II

注意这里fast从head开始,如果从head.next开始,fast==slow后,slow要再移动一步

// 处理null情况
if (head == null || head.next == null) return null; // 设置快慢节点
ListNode fast = head, slow = head; // 循环,直到fast或者fast.next等于null,或者fast追上slow
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (fast == slow) break;
}
// 检查退出循环的原因,如果是fast到了尽头,那么就返回null
if (fast != slow) return null; // slow和head开始继续移动,直到相遇
while (head != slow){
head = head.next;
slow = slow.next;
} return head;

160相交链表

思路:

  • 循环,只要两个节点不等
    • 如果p1为空,则p1 = headB
    • p2一样
  • 直接返回l1(l1为空,没交点,非空为相交点)

23合并k个排序链表

public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
if (n == 0) return null;
// 循环,直到剩下一个元素
// k作为间隔,遍历只需到n/2即可,每遍历一次,n/2到n的list就已经合并到前k = (n+1) / 2个里面,所以n要被替换为k
while (n > 1){
int k = (n+1) / 2;
for (int i = 0; i < n/2; i++){
lists[i] = merge(lists[i], lists[i+k]);
}
n = k;
}
return lists[0];
}

61旋转链表, 19删除链表的倒数第N个节点

输入: 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

思路:

  • 遍历一次,求链表长度len
  • 用k %= len求出断点与最后一个节点的距离
  • 设置快慢指针,先让它们分开k的距离,然后循环,让fast.next == null,即fast为最后一个节点。(这一步的思想可用于19删除链表的倒数第N个节点)
  • 让fast指向head,然后fast成为slow.next,然后slow断开链接
if (head == null || head.next == null) return head;

// 求长度
int size = 0;
ListNode p = head;
while (p != null){
size++;
p = p.next;
} // 获取间隔k
k %= size; ListNode slow = head, fast = head;
// 拉开距离
for (int i = 0; i< k; i++){
fast = fast.next;
} // 找到断点
while (fast.next != null){
slow = slow.next;
fast = fast.next;
} // 整理连接
fast.next = head;
fast = slow.next;
slow.next = null;
return fast;

82/83删除排序链表中的重复元素,203移除链表元素

删除重复多余的元素

思路:

  • 设置试探指针
  • 遍历,只要去重指针.next不为空
    • 如果与下一个相等,删除,否则移动
// 设置去重指针,从head开始,因为第一个元素不可能重复
ListNode cur = head; // 循环,只要指针没有到尽头
while (cur.next != null){
// 如果与下一个相等,删除,否则移动
if (cur.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}

删除出现重复的元素

思路:

  • 由于不能保证head是否出现重复,所以需要dummy
  • 需要去重指针(当前以及之前的节点已经去重,同理,由于无法保证head是否出现重复,去重指针从dummy开始)和试探节点
  • 遍历,只要去重指针.next不为null
    • 试探节点 = 去重节点.next
    • 试探节点判断下一个是否为空,并去掉所有重复的节点
    • 判断pre.next是否还是原来的cur,如果不是,说明经历过去重,去重节点直接指向试探节点的下一个节点。否则,说明试探节点指向了一个非重复节点,pre可以指向试探指针
dummy.next = head;
ListNode pre = dummy;
ListNode cur; // 遍历,只要pre.next不为空,说明还有需要探索的节点
while (pre.next != null){
cur = pre.next;
while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
if (pre.next != cur) pre.next = cur.next;
else pre = cur;
}
return dummy.next;

移除链表中节点值为target的元素

思路:与上面类似,需要dummy、合格指针(类似去重指针,其自身和前面的节点都不包含需要删除的节点)、试探指针

while (p.next != null){
cur = p.next;
if (cur.val == val) p.next = cur.next;
else p = cur;
}

138复制带随机指针的链表

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。

class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) { this.label = x; }
};

思路:

  • 先复制next
    • 按head.label新建newhead。然后把head和newhead放入map
    • 新建新旧指针(np,op)op从head.next起步
    • 循环,只要op不为空
      • 根据op.label新建newNode,并将op和newNode放入map
      • np指向newNode
      • op和np都移到下一个节点
  • 后复制random
    • np和op重回起点
    • 循环,只要op.next不为空
      • 将np.random指向map中根据op.random返回的节点
  • 返回newhead
if (head == null) return head;

Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode newHead = new RandomListNode(head.label);
map.put(head, newHead); RandomListNode np = newHead;
RandomListNode op = head.next;
while (op != null){
RandomListNode node = new RandomListNode(op.label);
map.put(op, node);
np.next = node;
np = np.next;
op = op.next;
} np = newHead;
op = head;
while (op != null){
np.random = map.get(op.random);
np = np.next;
op = op.next;
} return newHead;