24. 两两交换链表中的节点
LeetCode题目要求
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
解题思路
思路类似于单链表的反转,借助一个虚拟头节点,交换步骤为:
-1 -> 1 -> 2 -> 3 -> 4
- 缓存 3 这个节点
- -1 -> 2
- -1 -> 2 -> 1
- -1 -> 2 -> 1 -> 3 -> 4
- 处理下一次循环的节点,具体参考代码
/**
* 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;
}
if (head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode tmp = null;
while (pre.next != null && pre.next.next != null) { // -1 -> 1 -> 2 -> 3 -> 4
tmp = head.next.next; // tmp = 3 缓存
pre.next = head.next; // -1 -> 2
pre.next.next = head; // -1 -> 2 -> 1
head.next = tmp; // -1 -> 2 -> 1 -> 3
pre = head;
head = tmp;
}
return dummy.next;
}
}
重难点
附:学习资料链接
标签:24,pre,head,ListNode,val,Day4,next,链表,节点 From: https://www.cnblogs.com/blacksonny/p/17017580.html