leetCode-0024_两两交换链表中的节点

Posted on | In |

题目描述

英文题目

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

    Example:

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

    Note:

    • Your algorithm should use only constant extra space.
    • You may not modify the values in the list’s nodes, only nodes itself may be changed.
中文题目

  • 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

    示例:

    1
    给定 1->2->3->4, 你应该返回 2->1->4->3.

    说明:

    • 你的算法只能使用常数的额外空间。
    • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解决方法

方法一
  • 描述

还是需要建立dummy节点

  • 源码
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
42
43
/**
 两两交换链表中的节点 1->2->3->4
 
 @param head 不带头结点
 @return 交换之后的链表 2->1->4->3
 */
struct ListNode *swapPairs(struct ListNode *head)
{
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *prev = dummy;
    prev->next = head;
    
    while (prev->next != NULL && prev->next->next != NULL) {
        
        struct ListNode *a = prev->next;
        struct ListNode *b = prev->next->next;
        
        struct ListNode *temp = b->next;
        prev->next = b;
        b->next = a;
        a->next = temp;
        prev = a;
    }
    
    return dummy->next;
}

/**
 两两交换链表中的节点测试
 */
void swapPairs_test()
{
    SingleLinkListNode *head = single_link_list_create();
    single_link_list_insert_tail(head, 1);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 3);
    single_link_list_insert_tail(head, 4);
    
    printf("========两两交换链表中的节点测试========\n");
    single_link_list_dump_head(head);
    SingleLinkListNode *new = swapPairs(head->next);
    single_link_list_dump(new);
}

题目来源

Swap Nodes in Pairs

两两交换链表中的节点

线性表相关代码

数据结构-线性表