首页 > 代码库 > 【leetcode】Swap Nodes in Pairs

【leetcode】Swap Nodes in Pairs

2024-07-20 03:42:12   225人阅读

题目：

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解析：根据一个有序的链表，调换相邻两个节点，最后返回链表头。只能使用常数空间，并且不能只改变节点内部的值。主要思路是定义两个记录指针p1和p2，p1表示当前在链表中遍历到的需处理的节点位置，p2表示已经成功进行交换的链表中的末节点。

要注意两点：（1）因为链表中可能有偶数个节点，也可能有奇数个节点，要特别注意奇数个节点时的情况。

（2）链表间的链接和删除链接前后步骤顺序要注意，容易出错

Java AC代码：

public class Solution {

	public ListNode swapPairs(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode p1 = head;
		ListNode p2 = dummy;
		while (p1 != null && p1.next != null) {
			p2.next = p1.next;
			
			p1.next = p1.next.next;
			p2.next.next = p1;
			
			p2 = p2.next.next;
			p1 = p1.next;
			if (p1 == null) {
				return dummy.next;
			} else if(p1.next == null) {
				p2.next = p1;
				return dummy.next;
			}
		}
		return dummy.next;
	}

}



【leetcode】Swap Nodes in Pairs


联系
我们