LeetCode 第24题两两交换链表中的节点swapPairs

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

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

解题思路：

将整个链表分割为两个一组的小片段

参数说明：

curHead 当前结果链表的头节点

prevTail 前一段链表的结尾

n1 本段的第一个节点

n2 本段的第二个节点

n3 下一段的第一个节点

开始时候

 

 指针全部往后移动两格

 

 

 

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode curHead = head;
        ListNode prevTail=null;
        ListNode n1 = head;
        ListNode n2 = head.next;
        ListNode n3;
        while(n2!=null){
            n3 = n2.next;
            n2.next = n1;
            n1.next = n3;
            if(curHead==head){
                curHead = n2;
            }
            if(prevTail!=null){
                prevTail.next = n2;
            }
            prevTail = n1;
            n1 = n3;
            if(n3==null){
                break;
            }
            n2 = n3.next;
        }
        return curHead;
    }
}

Python代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        curHead = head
        prevTail = None
        n1 = head
        n2 = head.next
        while n2 is not None:
            n3 = n2.next
            n2.next = n1
            n1.next = n3
            if curHead == head:
                curHead = n2
            if prevTail is not None:
                prevTail.next = n2
            prevTail = n1
            n1 = n3
            if n3 is None:
                break
            n2 = n3.next
        return curHead