LeetCode - 24 两两交换链表中的节点

标题泉源

24. 两两交换链表中的节点 - 力扣（LeetCode）

标题形貌

给你一个链表，两两交换此中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的环境下完本钱题（即，只能举行节点交换）。

示例

示例 1：
   
  

1. <strong>输入：</strong>head = [1,2,3,4]
2. <strong>输出：</strong>[2,1,4,3]

复制代码

示例 2：
  

1. <strong>输入：</strong>head = []
2. <strong>输出：</strong>[]

复制代码

示例 3：
  

1. <strong>输入：</strong>head = [1]
2. <strong>输出：</strong>[1]

复制代码

提示

• 链表中节点的数目在范围 [0, 100] 内
  
• 0 <= Node.val <= 100
  

标题剖析

本题重要观察数据布局。

对于输入的链表，我们可以为其界说一个假造头节点 dummy_head，好比示例1，举行如下逻辑

C源码实现

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. struct ListNode* swapPairs(struct ListNode* head) {
9.     struct ListNode* dummy_head = (struct ListNode*)malloc(sizeof(struct ListNode));
10.     dummy_head->val = 0;
11.     dummy_head->next = head;
13.     struct ListNode* pre = dummy_head;
14.     struct ListNode* cur = pre->next;
16.     while (cur != NULL && cur->next != NULL) { // 由于要交换cur和cur.next两个节点，因此二者不能为null
17.         struct ListNode* nxt = cur->next;
19.         cur->next = nxt->next;
20.         nxt->next = cur;
21.         pre->next = nxt;
23.         pre = cur;
24.         cur = pre->next;
25.     }
27.     return dummy_head->next;
28. }

复制代码

C++源码实现

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution {
12. public:
13.     ListNode* swapPairs(ListNode* head) {
14.         ListNode* dummy_head = new ListNode(0, head);
16.         ListNode* pre = dummy_head;
17.         ListNode* cur = pre->next;
19.         while (cur != nullptr && cur->next != nullptr) { // 由于要交换cur和cur.next两个节点，因此二者不能为null
20.             ListNode* nxt = cur->next;
22.             cur->next = nxt->next;
23.             nxt->next = cur;
24.             pre->next = nxt;
26.             pre = cur;
27.             cur = pre->next;
28.         }
30.         return dummy_head->next;
31.     }
32. };

复制代码

Java源码实现

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
12. class Solution {
13.     public ListNode swapPairs(ListNode head) {
14.         ListNode dummy_head = new ListNode(0, head);
16.         ListNode pre = dummy_head;
17.         ListNode cur = pre.next;
19.         while (cur != null && cur.next != null) { // 由于要交换cur和cur.next两个节点，因此二者不能为null
20.             ListNode nxt = cur.next;
22.             cur.next = nxt.next;
23.             nxt.next = cur;
24.             pre.next = nxt;
26.             pre = cur;
27.             cur = pre.next;
28.         }
30.         return dummy_head.next;
31.     }
32. }

复制代码

Python源码实现

1. # Definition for singly-linked list.
2. # class ListNode(object):
3. #     def __init__(self, val=0, next=None):
4. #         self.val = val
5. #         self.next = next
6. class Solution(object):
7.     def swapPairs(self, head):
8.         """
9.         :type head: Optional[ListNode]
10.         :rtype: Optional[ListNode]
11.         """
12.         dummy_head = ListNode(0, head)
14.         pre = dummy_head
15.         cur = pre.next
17.         while cur and cur.next:  # 由于要交换cur和cur.next两个节点，因此二者不能为null
18.             nxt = cur.next
20.             cur.next = nxt.next
21.             nxt.next = cur
22.             pre.next = nxt
24.             pre = cur
25.             cur = pre.next
26.         
27.         return dummy_head.next
28.         

复制代码

JavaScript源码实现

1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val, next) {
4. *     this.val = (val===undefined ? 0 : val)
5. *     this.next = (next===undefined ? null : next)
6. * }
7. */
8. /**
9. * @param {ListNode} head
10. * @return {ListNode}
11. */
12. var swapPairs = function (head) {
13.     const dummy_head = new ListNode(0, head);
15.     let pre = dummy_head;
16.     let cur = pre.next;
18.     while (cur != null && cur.next != null) { // 由于要交换cur和cur.next两个节点，因此二者不能为null
19.         const nxt = cur.next;
21.         cur.next = nxt.next;
22.         nxt.next = cur;
23.         pre.next = nxt;
25.         pre = cur;
26.         cur = pre.next;
27.     }
29.     return dummy_head.next;
30. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告