【LeetCode】24. 两两交换链表中的节点（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 || head.next == null) return head; //三指针 ListNode before = null; ListNode cur = head; ListNode after = head.next; //交换后，head的next节点为新的头节点（保存新的头节点） head = head.next; while (cur != null && after != null) { //当前节点的next指向下下个节点 cur.next = after.next; after.next = cur; //cur和after交换后，如果before为空，就让其指向cur if (before == null) before = cur; //否则让它的下个节点指向after，因为cur和after交换后，cur的前一个其实还是指向cur的，我们需要让其指向after，所以有了第三个指针before else { before.next = after; before = cur; } cur = cur.next; if (cur == null) break; after = cur.next; } return head; } }

解法二

递归

/** * 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 || head.next == null) return head; ListNode next = head.next; //递归next的下个节点，因为head和next是要在当前交换的，所以不能传递（这一步是难点） head.next = swapPairs(next.next); //指回head next.next = head; //此时next为头节点 return next; } }

写完解法一后，看了题解区画手大鹏的题解，我只想说一句，这也能用递归。。。果然还是太菜了，想不到。