[数据结构与算法]【链表专题】—— 两两交换链表中的节点

# LeetCode 24：两两交换链表中的节点

• 利用指针交换的思想，属于链表中比较基础的算法

• 主要思想：

对于没有头结点的链表问题最好定义一个虚拟头结点
当链表为空和链表只有一个结点的时候，无需进行交换

创建一个头结点连接到链表上，通过循环遍历链表
只要链表满足pro.next != null && pro.next.next != null就一直循环下去

主要的结点交换步骤：（此处pro为头结点，head为第一个结点）

//创建一个临时结点保存第二个结点的指针域
ListNode temp = head.next.next;
pro.next = head.next;
head.next.next = head;
head.next = temp;

更新pro和head的位置

pro = head; 
head = head.next;

最后返回从第一个结点开始的链表即可 return dummyNode.next;

代码部分：

/**
 * 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) {
        //创建一个虚拟结点作为头结点
        ListNode dummyNode = new ListNode(0, head);

        //定义一个指针指向头结点
        ListNode pro = dummyNode;

        //循环完成指针交换
        while(pro.next != null && pro.next.next != null){
        
            //创建一个临时节点,保存第二个节点的next
            ListNode temp = head.next.next;
            pro.next = head.next; //头结点指向第二个结点
            head.next.next = head; //第二个结点指向第一个结点
            head.next = temp; //更新第一个结点的指针域为第二个结点的指针域
            
            //更新指针的指向
            pro = head;
            head = head.next;
        }

        return dummyNode.next;
       
    }
}