【LeetCode】链表相加 进位

 

 

/**
 * 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 pre =  new ListNode(0); //开辟新的内存空间，pre指向该内存空间，pre是该结果链表的头节点
        ListNode cur = pre; //定义一个可移动的指针，也指向该内存空间，后续添加节点依赖该指针
        int carry = 0; //进位

        while(l1!=null || l2!=null){
            int x = l1 != null ? l1.val : 0; //获取对应位置上的值，如果某个位置上为空，则赋值为0
            int y = l2 != null ? l2.val : 0;

            int sum = x + y + carry; //l1和l2对应位置上的值以及进位的值相加

            carry = sum / 10; //获取每次相加后的进位
            sum = sum % 10; //获取进位后的值

            cur.next = new ListNode(sum); //创建一个新的节点，该节点的值为相加进位后的值，并且结果链表的指针指向该节点
            cur = cur.next; //结果链表指针向前移动，pre头指针没有动

            if(l1!= null){
                l1 = l1.next;
            }
            if(l2!= null){
                l2 = l2.next;
            }
        }
        if(carry == 1){ 
            cur.next = new ListNode(carry); //如果最后加完后还有进位（进位值一定为1），则创建新的节点，保存该节点
        }
        return pre.next;//返回结果链表，因为pre指向该链表头指针，头指针处的值为0，头指针的下一个节点才是结果链表的首元节点
    }
}

开辟新的链表空间 ListNode pre = new ListNode(0)   pre为头节点指针

 

最后返回的是return pre.next    pre.next指向结果链表的首元节点

 

 不使用头结点，直接返回结果链表方法