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

/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• }; */

class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 / ListNode addInList(ListNode* head1, ListNode* head2) { // write code here ListNode* back = head1; ListNode* midde = head1; ListNode* front = head1; ListNode* newhead = NULL;

//List 1 的翻转

if (back != NULL)
{
	midde = back->next;
	if (midde != NULL)
	{
		front = midde->next;
	}
	else
		front = NULL;
}
else
{
	midde = NULL;
	front = NULL;
}

while (midde)
{
	if (back == head1)
		back->next = NULL;
	midde->next = back;
	back = midde;
	midde = front;
	if (front != NULL)
		front = front->next;
}

head1 = back;
//cout << "翻转后的 head1\n";
//showList(head1);


// List 2 的翻转

back = head2;
if (back != NULL)
{
	midde = back->next;
	if (midde != NULL)
	{
		front = midde->next;
	}
	else
		front = NULL;
}
else
{
	midde = NULL;
	front = NULL;
}

while (midde)
{
	if (back == head2)
		back->next = NULL;
	midde->next = back;
	back = midde;
	midde = front;
	if (front != NULL)
		front = front->next;
}

head2 = back;
//cout << "反转后的 head2\n";
//showList(head2);



back = head1;
midde = head2;

// 建立新头结点  且 head1 与 head2 都不为空
newhead = head1;
front = newhead;
int h = 1;
while (back && midde)
{

	if ((back->val + midde->val) >= 10)
	{
		if (back->next != NULL)
		{
			back->next->val += 1;
		}
		
		else 
		{
			if (midde->next != NULL)
			{
				midde->next->val += 1;
			}
		}
		 
		if (back->next == NULL && midde->next == NULL)
		{
			front->next = new ListNode(0);
			front = front->next;
			front->val = (back->val + midde->val) % 10;
			front->next = new ListNode(0);

			front = front->next;
			front->val = 1;
			front->next = NULL;
			break;
		}
		

		back->val = (back->val + midde->val) % 10;

		if (front == newhead && h == 1)
		{
			newhead = back;
			h = 0; 
		}
		else
		{
			front->next = back;
			front = front->next;
		}

		 

		back = back->next;
		midde = midde->next;
	}
	else
	{
		back->val += midde->val;

		if (front == newhead && h == 1)
		{
			newhead = back;
			h = 0;
		}
		else
		{
			front->next = back;
			front = front->next;
		}

		back = back->next;
		midde = midde->next;
		 
	}
}
// 进行完后两个链表一样长将尾部指向 NULL 新的头指针不为空
if (!back && !midde && newhead)
{
	front->next = NULL;
}

// head1 是 NULL head2 不是 NULL 
if (!back && midde)
{
	if (front == newhead && h == 1)
	{
		newhead = midde;
		front = newhead;
		midde = midde->next;
		h = 0;
	}
	while (midde)
	{
		if (midde->val >= 10)
		{
			midde->val = midde->val % 10;
			if (midde->next == NULL)
			{
				midde->next = new ListNode(0);
				midde->next->next = NULL;
			}
			midde->next->val += 1;
		}
		front->next = midde;
		midde = midde->next;
		front = front->next;
	}
	front->next = NULL;
}

// head1 不是 NULL head2 是 NULL  还要进行是否大于 10 的验算
if (back && !midde)
{
	if (front == newhead && h == 1)
	{
		newhead = back;
		front = newhead;
		back = back->next;
		h = 0;
	}
	while (back)
	{
		if (back->val >= 10)
		{
			back->val = back->val % 10;
			if (back->next == NULL)
			{
				back->next = new ListNode(0);
				back->next->next = NULL;
			}
			back->next->val += 1;
		}
		 
			front->next = back;
			back = back->next;
			front = front->next;
		 
	}
	front->next = NULL;
}

if (!head1 && head2)
	newhead = head2;
if (head1 && !head2)
	newhead = head1;

//cout << "加好后的newhead\n";
//showList(newhead);
// 将加好的链表重新翻转

back = newhead;
if(back != NULL)
if (back->next)
{
	midde = back->next;
	if (midde->next)
		front = midde->next;
	else
	{
		front = NULL;
	}
}
else
{
	midde = back->next;
	front = back->next;
}

while (midde)
{
	if (back == newhead)
	{
		back->next = NULL;
	}
	midde->next = back;
	back = midde;
	midde = front;
	if(front)
	front = front->next;
}

newhead = back;


return newhead;
}

};