LeetCode----Swap Nodes in Pairs

来源:互联网 时间:1970-01-01

Swap Nodes in Pairs

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.

分析:

交换链表相邻的元素,使用常数个空间,而且不能使用链表节点值交换,只能节点间交换。

给定两个相邻的节点进行交换其实并不难,但是,需要将这交换的节点与整个链表连接起来。

为了能够连接起来,我们需要一个前驱(pre)节点来记录相邻交换的节点的前驱,还需要一个后继(t)节点记录这两个节点的后继节点,然后将它们连接起来。

代码:

class Solution(object): def swapPairs(self, head):""":type head: ListNode:rtype: ListNode"""p = headif p is None or p.next is None: return pq = p.nexthead = qpre = ListNode(-1)while p and q: t = q.next q.next = p p.next = t pre.next = p pre = q if t and t.next:p = tq = t.next else:breakreturn head



相关阅读:
Top