题解 | #链表相加(二)#

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
function addInList( $head1 ,  $head2 )
{
    // write code here
    if($head1 == null){
        return $head2;
    }
    if($head2 == null){
        return $head1;
    }
    //反转两个链表
    $p1 = reverseList($head1);
    $p2 = reverseList($head2);
    $p = null;
    $res = $p;
    $flag = 0;
    while($p1 || $p2){
        if($p1){
            $p1v = $p1->val;
        }else{
            $p1v = 0;
        }
        if($p2){
            $p2v = $p2->val;
        }else{
            $p2v = 0;
        }
        $value = $p1v+$p2v+$flag;
        if($value>9){
            $flag = 1;
            $value = $value-10;
        }else{
            $flag = 0;
        }
        if($res == null){
            $res = new ListNode(0);
            $res->val = $value;
            $res->next = null;
            $p = $res;
        }else{
            $tmp = new ListNode(0);
            $tmp->val = $value;
            $tmp->next = null;
            $p->next = $tmp;
            $p = $p->next;
        }
        if($p1){
            $p1 = $p1->next;
        }
        if($p2){
            $p2=$p2->next;
        }
    }
    if($flag==1){
        $tmp = new ListNode(0);
        $tmp->val =1;
        $tmp->next =null;
        $p->next = $tmp;
    }
    $res = reverseList($res);
    return $res;
}
//单链表逆置
function reverseList($list){
    $p = $list;
    $pre = null;
    while($p){
        $next = $p->next;
        $p->next = $pre;
        $pre = $p;
        $p = $next;
    }
    return $pre;
}

考察点：单链表逆置，相加后输出，注意点是最后一次进位即flag=1时，需要新增一个节点。