给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
解题思路:
- 首先建立一个虚拟的结点,用于来交换指针的
- 使得虚拟结点指向头结点- 给虚拟结点赋值给pre指针
- 只要头结点和头结点的下一个结点都不为空,那就交换firstNode和secodeNode,继续将虚拟结点赋为此时的firstNode,头结点head指向它的下一个结点,依次遍历完整个链表,这样子就实现了两两互相交换
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; while((head != null) && (head.next != null)){ ListNode firstNode = head; ListNode secondNode = firstNode.next; pre.next = secondNode; firstNode.next = secondNode.next; secondNode.next = firstNode; pre = firstNode; head = firstNode.next; } return dummy.next; } }
运行效率截图: