Created
August 9, 2022 06:48
-
-
Save alvinlau/99a1cc2763951ea79e9d21d2dccd4949 to your computer and use it in GitHub Desktop.
24. Swap Nodes in Pairs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # https://leetcode.com/problems/swap-nodes-in-pairs/ | |
| # Runtime: 81 ms, faster than 92.68% of Ruby online submissions for Swap Nodes in Pairs. | |
| # Memory Usage: 211.1 MB, less than 18.70% of Ruby online submissions for Swap Nodes in Pairs. | |
| # 24. Swap Nodes in Pairs | |
| # 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 | |
| # Definition for singly-linked list. | |
| # class ListNode | |
| # attr_accessor :val, :next | |
| # def initialize(val = 0, _next = nil) | |
| # @val = val | |
| # @next = _next | |
| # end | |
| # end | |
| # @param {ListNode} head | |
| # @return {ListNode} | |
| def swap_pairs(head) | |
| return head unless head && head.next | |
| final = head.next | |
| result = step(nil, head) | |
| while result[:rest] | |
| result = step(result[:prev], result[:rest]) | |
| end | |
| final | |
| end | |
| def step(prev, curr) | |
| one = curr | |
| two = one.next | |
| return {rest: nil} unless two | |
| rest = two.next | |
| two.next = one | |
| one.next = rest | |
| prev.next = two if prev | |
| {prev: one, rest: rest} | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment