当前位置：首页 > article >正文

C语言笔试题之两数相加（多次反转链表实现）

article 2024/11/15 15:51:24

实例要求：

1、给定两个非空链表（l1和l2）来代表两个非负整数；
2、数字最高位位于链表开始位置；
3、它们的每个节点只存储一位数字；
4、将这两数相加会返回一个新的链表；

案例展示：

在这里插入图片描述

实例分析：

1、编写反转链表函数，反转链表l1和l2；
2、创建虚拟头节点；
3、新建节点表示当前节点指针；
4、计算进位和取个位数；
5、连接新节点和更新当前节点指针；
6、反转链表，得到最终结果；
7、释放虚拟头节点的内存；

示例代码：

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {
	 *     int val;
	 *     struct ListNode *next;
	 * };
	 */
	
	
	// 反转链表函数
	struct ListNode* reverseList(struct ListNode* head) {
		
		if(head == NULL || head->next == NULL){
		    return head;
		}
		
		struct ListNode *p = head;
		struct ListNode *q = p->next;
		 
		p->next = NULL;
		 
		while(q){
		 
		    p = q->next;
		    q->next = head;
		    head = q;
		    q = p;
		 
		}
		
		return head;
		
	}
	
	// 将两个链表表示的非负整数相加
	struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
	{
	    l1 = reverseList(l1); // 反转链表l1
	    l2 = reverseList(l2); // 反转链表l2
	
	    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建虚拟头节点
	    dummy->val = 0;
	    dummy->next = NULL;
	    struct ListNode *curr = dummy; // 当前节点指针
	    int carry = 0; // 进位
	
	    while (l1 || l2 || carry) 
	    {
	        int sum = carry;
	        if (l1 != NULL) {
	            sum += l1->val;
	            l1 = l1->next;
	        }
	        if (l2 != NULL) {
	            sum += l2->val;
	            l2 = l2->next;
	        }
	        carry = sum / 10; // 计算进位
	        struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建新节点
	        newNode->val = sum % 10; // 取个位数
	        newNode->next = NULL;
	        curr->next = newNode; // 连接新节点
	        curr = curr->next; // 更新当前节点指针
	    }
	
	    struct ListNode *result = reverseList(dummy->next); // 反转链表，得到最终结果
	    free(dummy); // 释放虚拟头节点的内存
	    return result;
	}