GVKun编程网logo

PHP实现链表两数相加（php实现链表操作）

13

关于PHP实现链表两数相加和php实现链表操作的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于002.两数相加、2#两数相加、2-两数相加、2.两数相加等相关知识的信息别忘了在本站进行查找

关于PHP实现链表两数相加和php实现链表操作的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于002.两数相加、2#两数相加、2-两数相加、2. 两数相加等相关知识的信息别忘了在本站进行查找喔。

本文目录一览：

PHP实现链表两数相加（php实现链表操作）

PHP实现链表两数相加（php实现链表操作）

该题目来自leetcode 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2->4->3) + (5->6->4)
输出：7->0->8
原因：342 + 465 = 807

以下是解题代码：

/**
 *  定义一个单链表
 */
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

/**
 * 实现两数相加
 *
 * @param ListNode $l1
 * @param ListNode $l2
 * @return ListNode
 */
function addTwoNumbers(ListNode $l1, ListNode $l2) {
    $dummyHead = new ListNode(0);
    $p = $l1; 
    $q = $l2; 
    $curr = $dummyHead;
    $carry = 0;
    while ($p != null || $q != null) {
        $x = ($p != null) ? $p->val : 0;
        $y = ($q != null) ? $q->val : 0;
        $sum = $carry + $x + $y;
        $carry = intval($sum / 10); // 按10进位
        $curr->next = new ListNode($sum % 10);
        $curr = $curr->next;
        if ($p != null) $p = $p->next;
        if ($q != null) $q = $q->next;
    }

    // 最后两数相加有进位处理
    if ($carry > 0) {
        $curr->next = new ListNode($carry);
    }
    return $dummyHead->next;
}

/**
 * 链表转数组
 *
 * @param ListNode $data
 * @return array
 */
function listToArray(ListNode $data)
{
    $result = [];
    while ($data != null) {
        $result[] = $data->val;
        $data = $data->next;
    }

    return $result;
}

/**
 * 数组转链表
 *
 * @param array $data
 * @return ListNode
 */
function arrayToList($data)
{  
    $result = new ListNode(0);

    if (!empty($data)) {
        $result = new ListNode(array_shift($data));
        $current = $result;
        foreach ($data as $val) {
            $current->next = new ListNode($val);
            $current = $current->next;
        }
    }

    return $result;
}

$l1 = arrayToList([2, 4, 6]);
$l2 = arrayToList([5, 6, 4]);

var_dump(listToArray(addTwoNumbers($l1 , $l2)));

002.两数相加

002.两数相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8        342+465 = 807

  • 题目描述：输入两个非空单链表，链表的每个结点的值是一个1位数整数，两个链表都是一个大整数每一位的逆序排序，求这两个链表代表的整数的和的链表值；

  • 思路：1. 获取到两个数 然后相加 再新建list写入。2.每位想加时候考虑进位标志位
def addTwoNumbers(L1,L2):
	move = 0
	while L1:
		numOfL1 = L1.val * 10**move
		move += 1
		L1 = L1.next
	move = 0
	while L2:
		numOfL2 = L2.val * 10**move
		move += 1
		L2 = L2.next
	final = numOfL1 + numOfL2
	h = m = ListNode(0)
	if not final:
		return h
	while final:
		m.next = ListNode(final % 10)
		final = final/10
		m = m.next  # m.next 默认为空
	return h.next

# 带进位标志位的 函数 挺好
def addTwoNumbers(L1,L2):
	if L1 is None:
		return L2
	if L2 is None:
		return L1
	tmp = ListNode(0) # 最终要用的
	res = tmp
	flag = 0 #进位标记位
	while L1 or L2:
		tmpsum = 0
		if L1:
			tmpsum = L1.val
			L1 = L1.next
		if L2:
			tmpsum += L2.val
			L2 = L2.next
		tmpres = ((tmpsum + flag) % 10) # 余数
		flag = ((tmpsum + flag) // 10) # 进位
		res.next = ListNode(tmpres)
		res = res.next
	if flag:
		res.next = ListNode(1)
	res = tmp.next
	return res

 

本文同步分享在 博客“SoWhat1412”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

2#两数相加

2#两数相加

题目描述

2#两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

由于是两个链表的元素对应相加，很自然地就想到用双指针，然后在双指针的基础上加一些进位的操作满足特殊情况。

1. 结果位数与有原链表相等

这是一种比较简单的情况，原题中的测试用例就是这种。虽然在中间的某一位会有进位，但是最高位之和比较小，不会产生进位，最后的和的结果的位数也和两个加数中较长的那个一致。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

这种情况的处理就比较简单。新建一个链表，设置一个int型的变量carry来保存进位的信息，使用两个指针分别遍历两个链表，取出每一位的值（细节：如果指针变为null了，取出的值为0），依次在链表的尾部添加每一位的结果。

2. 结果位数与原链表不等

这种情况，最高位比较大，最后的结果会比两个加数中较大的那个还多一位。

Input: (9 -> 9) + (1)
Output: 0 -> 0 -> 1
Explanation: 99 + 1 = 100.

在这种情况下，最后要多一步操作，判断carry位是否为0，如果不为0，就要在结果链表的尾部再加一位。

源码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode result = new ListNode(0);
        ListNode current = result;
        while (l1 != null || l2 != null){
            int x = (l1 != null)? l1.val : 0;  // 取出对应位的值
            int y = (l2 != null)? l2.val : 0;
            int sum = x + y + carry;
            current.next = new ListNode(sum % 10);
            carry = sum / 10;            // 计算进位
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
            current = current.next;

        }
        if (carry > 0) // 判断是否需要多加一位
            current.next = new ListNode(carry);
        
        return result.next;
        
    }
}

2-两数相加

2-两数相加

#暴力解法 时间复杂度 O(max(m,n)) 空间复杂度 O(max(m,n))+1

# 创建结点
cur = head = ListNode(0)
carry = 0
# 遍历l1和l2链表
while l1 or l2:
    # 创建结点
    newPoint = ListNode(0)
    if not l1:
        Sum = l2.val + carry
        newPoint.val = Sum % 10
        carry = Sum// 10
        l2 = l2.next
    elif not l2:
        Sum = l1.val + carry
        newPoint.val = Sum % 10
        carry = Sum// 10
        l1 = l1.next
    else:
        Sum = l1.val + l2.val + carry
        newPoint.val = Sum % 10
        carry = Sum //10
        l1 = l1.next
        l2 = l2.next
    head.next = newPoint
    head = head.next
if carry:
    newPoint = ListNode(1)
    head.next = newPoint
return cur.next

2. 两数相加

2. 两数相加

给定两个非空链表来代表两个非负数，位数按照逆序方式存储，它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *ans = new ListNode(0);  //答案串     
        ListNode *head = ans;//记录一下答案串的首地址
        int pos = 0; //标记进位
        while (l1 && l2) {//现将相同的位置加上
            int cnt = l1 -> val + l2 -> val + pos;
            pos = cnt > 9 ? 1 : 0;
            ans -> val = cnt % 10;
            l1 = l1 -> next;
            l2 = l2 -> next;
            if (l1 && l2) {
                ans -> next = new ListNode(0);
                ans = ans -> next;
            } else {
                break;
            }
        }      
        // 然后处理后边的数此时ans不是空的，而是指向最后一个节点
        if (l1 == NULL && l2 == NULL) {//加完了
            if (pos) {
                ans -> next = new ListNode(0);
                ans = ans -> next;
                ans -> val = pos;
            }  
        } else if (l1 == NULL) {//第一个链表用完了
            while (l2) {//用完
                ans -> next = new ListNode(0);
                ans = ans -> next;
                int cnt = l2 -> val + pos;
                pos = cnt > 9 ? 1 : 0;
                ans -> val = cnt % 10;
                l2 = l2 -> next;
            } 
            if (pos) {
                ans -> next = new ListNode(0);
                ans = ans -> next;
                ans -> val = pos;
            } 
        } else if (l2 == NULL) {
            while (l1) {//用完
                ans -> next = new ListNode(0);
                ans = ans -> next;
                int cnt = l1 -> val + pos;
                pos = cnt > 9 ? 1 : 0;
                ans -> val = cnt % 10;
                l1 = l1 -> next;
            } 
            if (pos) {
                ans -> next = new ListNode(0);
                ans = ans -> next;
                ans -> val = pos;
            }
        }
        ans = head;
        return ans;     
    }
};

 

今天关于PHP实现链表两数相加和php实现链表操作的分享就到这里，希望大家有所收获，若想了解更多关于002.两数相加、2#两数相加、2-两数相加、2. 两数相加等相关知识，可以在本站进行查询。

本文标签：

上一篇AndroidStudio3.0 Error:Execution failed for task '':app:processDebugResources''.

下一篇docker 镜像拉取错误 Error response from daemon: Get https://registry-1.docker.io/v2/library

相关文章