leetcode简单题4

发表于   |   分类于   |  

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL)
        {
            return l2;
        }
        if(l2==NULL)
        {
            return l1;
        }
        ListNode* head=(ListNode*)malloc(sizeof(ListNode));
        ListNode* p=head;
        ListNode* p1=l1;
        ListNode* p2=l2;
        while(p1!=NULL&&p2!=NULL)
        {
            if(p1->val<p2->val)
            {
                p->next=p1;
                p=p->next;
                p1=p1->next;
            }
            else
            {
                p->next=p2;
                p=p->next;
                p2=p2->next;
            }
        }
        if(p1==NULL)
        {
            p->next=p2;
        }
        else
        {
            p->next=p1;
        }
        return head->next;
    }
};

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	ListNode* p1 = head;
	ListNode* p2 = head->next;
	ListNode* pre = (ListNode*)malloc(sizeof(ListNode));
	pre->next = p1;
	ListNode* newHead = head->next;
	while (p1 != NULL&&p2 != NULL)
	{
		pre->next = p2;
		p1->next = p2->next;
		p2->next = p1;

		pre = p1;
		p1 = p1->next;
		if (pre->next != NULL&&p1->next!=NULL)
		{
			p2 = p1->next;
		}
		else
		{
			break;
		}
	}
	return newHead;
}
};