LeetCode 24. Swap Nodes in Pairs 20170424

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.

Subscribe to see which companies asked this question.

Show Tags

Show Similar Problems

 题目大意：将链表中的节点两两交换，比如给定1->2->3->4，变换之后变为2->1->4->3.

解题思路：为了计算方便可以加入一个头结点，比如0->1->2->3->4。比较原始列表和变换列表，可知道变换后结果为0->2->1->3，需要将0的结点指向下一个结点的指针指向2结点，1结点指向下一个结点的指针指向3，然后2结点指针指向1结点。此时用一个begin结点代表起点0结点，用before和after表示每对需要调换的对子的第一个结点。第一次变化时，结束该次变换后before标记的结点往右移一位，after的标记的结点往后移两位，后面的变化中before和after标记的结点每次都往后移两位

 

# Definition for singly-linked list.
# class ListNode(object):
　　# def __init__(self, x):
　　　　# self.val = x
　　　　# self.next = None

class Solution(object):
　　def swapPairs(self, head):
　　　　"""
　　　　:type head: ListNode
　　　　:rtype: ListNode
　　　　"""
　　　　begin = ListNode(0)
　　　　begin.next = head
　　　　before, after = begin, head
　　　　while after and after.next:
　　　　　　before.next = after.next
　　　　　　after.next = before.next.next
　　　　　　before.next.next = after
　　　　　　before, after = after,after.next
　　　　return begin.next