💕"轻舟已过万重山"💕
作者：Mylvzi
文章主要内容：算法系列–链表刷题(二)
今天为大家带来的是
算法系列--链表刷题(二),带来了几道经典的有关链表的面试题(合并K个有序列表)
1.两数相加
模拟两数相加:
使用两个指针cur1和cur2来遍历两个链表,通过t记录每次相加的结果,最后创建出新的节点,尾插
注意:
- 每次相加时都需要更新
t的值,但是不可以直接将t设置为0,因为存在进位的可能,比如t = 9 + 9 = 18,要插入节点的val = 8,还要记录进位1,所以:val = t % 10, t /= 10 - 循环的结束要同时
满足三个条件,cur1 = null, cur2 = null, t = 0,其中最后t = 0这种情况最容易忘记,导致最后需要进位没进位成,结果相比于正确答案少了一位
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode cur1 = l1; ListNode cur2 = l2; ListNode phead = new ListNode(0); ListNode cur = phead;// 用于尾插 int t = 0;// 用于表示本次相加的结果 处理进位 // 要注意t最后可能不为0 要进一位 while(cur1 != null || cur2 != null || t != 0) { // 加上第一个节点 if(cur1 != null) { t += cur1.val; cur1 = cur1.next; } // 加上第二个节点 if(cur2 != null) { t += cur2.val; cur2 = cur2.next; } ListNode newNode = new ListNode(t % 10); t /= 10; // 尾插 cur.next = newNode; cur = newNode; } return phead.next; } }
2.两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
思路:
- 分别得到下标为奇数的所有节点的组合和下标为偶数的所有节点的组合(下标从1开始)
- 按照偶数节点在前,奇数节点在后的顺序合并两个链表
- 得到新的链表
代码实现:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; // 定义两个虚拟节点 分别接收奇数和偶数的节点 ListNode p1 = new ListNode(0); ListNode p2 = new ListNode(0); ListNode cur1 = p1; ListNode cur2 = p2; ListNode cur = head; int i = 1; // 分别得到奇数和偶数的链表组合 while(cur != null) { ListNode newNode = new ListNode(cur.val); if(i % 2 != 0) { // 奇数 cur1.next = newNode; cur1 = newNode; }else { // 偶数 cur2.next = newNode; cur2 = newNode; } cur = cur.next; i++; } // 合并两个链表 ListNode p3 = new ListNode(0); ListNode t1 = p1.next; ListNode t2 = p2.next; ListNode cur3 = p3; while(t1 != null || t2 != null) { if(t2 != null) { cur3.next = t2; cur3 = t2; t2 = t2.next; } if(t1 != null) { cur3.next = t1; cur3 = t1; t1 = t1.next; } } return p3.next; } }
注:本题更加简洁的写法是通过递归实现的,感兴趣的可以去我的算法系列里查看
3.重排链表
思路:
- 首先获得中间节点,以中间节点为基准,分为两个不同的链表l1和l2
- 逆序l2
- 合并两个链表
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { ListNode slow = head, fast = head; // 找到中间节点 while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode l1 = head; ListNode l2 = slow.next; slow.next = null; // 逆序第二个节点 l2 = reverseList(l2); ListNode phead = new ListNode(0); ListNode cur = phead; // 合并两个链表 while(l1 != null || l2 != null) { if(l1 != null) { cur.next = l1; cur = l1; l1 = l1.next; } if(l2 != null) { cur.next = l2; cur = l2; l2 = l2.next; } } head = phead.next; } public ListNode reverseList(ListNode head) { if(head == null) return null; if(head.next == null) return head; ListNode pHead = new ListNode(0); ListNode cur = head; while(cur != null) { ListNode curNext = cur.next; cur.next = pHead.next; pHead.next = cur; cur = curNext; } return pHead.next; } }
同样的本题也有更加简洁的递归写法
算法系列--链表刷题(二)（下）https://developer.aliyun.com/article/1480813?spm=a2c6h.13148508.setting.24.361f4f0eyTL4lb
