Leetcode 24. 两两交换链表中的节点

野性酷女 2022-09-05 06:10 180阅读 0赞

#### 题目重述 ####

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

##### 示例 1： #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]

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

输入：head = \[\]  
输出：\[\]  
示例 3：

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

提示：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

核心思想就是遍历，每次走两步，交换即可，为了连起来，我们需要保存前驱节点，而为了更方便一点，我们可以设置一个虚的头结点，方便统一操作

#### Java实现 ####

class Solution {
        
        // 1,2,3
        public ListNode swapPairs(ListNode head) {
        
            if(head == null){
        
                return null;
            }
            // p的前驱节点，虚结点，方便操作
            ListNode pre = new ListNode(0,head);
            ListNode p = head;
            while (p != null &&p.next !=null){
        
    
                // 保存要交换的结点，开始交换
                ListNode tmp = p.next;
                p.next = p.next.next;
                tmp.next = p;
                pre.next = tmp;
                // 交换后，头节点就不是原来的头节点了，所以第一次操作需要，保存头节点
                if(p == head){
        
                    head = tmp;
                }
                pre = p;
                p = p.next;
            }
            return head;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20220829/03270bfec4b34cdf9893a97d57f05e83.png