美文网首页@IT·互联网
Leetcode24:两两交换链表中的节点

Leetcode24:两两交换链表中的节点

作者: 我可能是个假开发 | 来源:发表于2024-02-03 14:27 被阅读0次

    一、题目

    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
    示例:

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

    相关文章

      网友评论

        本文标题:Leetcode24:两两交换链表中的节点

        本文链接:https://www.haomeiwen.com/subject/rwdxadtx.html