一、题目
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
输入:head = []
输出:[]
输入:head = [1]
输出:[1]
二、题解
思路:让一个指针指向要交换的两个节点的前一个节点(cur),每次让两个要交换的节点的后一个节点来到cur的后面。cur指针再向前移动两位。直到cur的后一位没有元素(奇数个元素)或者cur的后一位的后一位没有元素(偶数个元素)
因为第一个节点没有前一个元素,所以设置一个虚拟头节点,方便第一个元素和后面的元素能走相同的逻辑。
第一遍循环.png 第二遍循环.png
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//进位标志
int carry = 0;
//开头的节点
ListNode head = null;
//指向上一个节点
ListNode last = null;
while (l1 != null || l2 != null){
int val = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);
//该位置上的数
int cur = val + carry;
Integer remainder = null;
if ((cur / 10) > 0) {
//有进位 余数
remainder = cur % 10;
}
//求和之后的新节点
ListNode newNode = new ListNode(remainder != null ? remainder : cur);
if (head == null) {
//一开始的头节点
head = newNode;
} else {
last.next = newNode;
}
last = newNode;
//存储进位信息 给下一次相加使用
carry = cur / 10;
l1 = (l1 == null ? null : l1.next);
l2 = (l2 == null ? null : l2.next);
}
//循环结束了如果carry还有值,说明最后还进了一位,再增加一个节点
if (carry == 1) {
last.next = new ListNode(carry, null);
}
return head;
}
}
网友评论