24. Swap Nodes in Pairs

Medium

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output:
 [2,1,4,3]

Example 2:

Input: head = []
Output:
 []

Example 3:

Input: head = [1]
Output:
 [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].

• 0 <= Node.val <= 100

解題

Run time beat 100%、不需要做 Recursion，時間複雜度是O(n)的解法～

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head==nil || head.Next==nil { return head }
    header := head.Next
    
    fast, slow, pre := head.Next, head, head
    
    slow.Next = fast.Next
    fast.Next = slow
    
    for slow.Next!=nil && slow.Next.Next!=nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next.Next
        
        slow.Next = fast.Next
        fast.Next = slow
        pre.Next = fast
    }

    
    return header
}