LeetCode【24.两两交换链表中的节点】

- 日理万妓 2022-05-07 03:52 153阅读 0赞

### 题目描述： ###

> 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

**示例**：

*  给定  1 − > 2 − > 3 − > 4 1->2->3->4 1−>2−>3−>4，你应返回 2 − > 1 − > 4 − > 3. 2->1->4->3. 2−>1−>4−>3.

**思路 \* 1**  
使用`prev1`指针来计数，每两个节点停一次并指向两个节点后的下一个节点，然后又分了两种情况：`count`正好等于2，此时，用一个头插法的思路来依次插入节点,这样就相当于反转了一下链表，新初始的的指针`cur`也需要前进2次；`count`小于2时，直接使`cur.next`指向上次的`prev2`就可以啦。这个思路可以用于后面的一题`k个一组进行翻转`。

**代码 \* 1**

class Solution { 
        public ListNode swapPairs(ListNode head) { 
            ListNode cur = new ListNode(-1);
            ListNode dummpy = cur, prev1 = head, prev2 = head;
            int k = 2;
            while(prev1 != null) {  
                int count = 0;
                while(count < k && prev1 != null) { 
                    ++ count;
                    prev1 = prev1.next;
                }
                int count1 = k;
                if(count == k) {   
                    ListNode prev3 = null;
                    while(count > 0 && prev2 != null) { 
                        prev3 = prev2.next;
                        prev2.next = cur.next;
                        cur.next = prev2;
                        prev2 = prev3;
                        count --;
                    }
                    while(count1 > 0) { 
                        count1 --;
                        cur = cur.next;
                    }
                }else { 
                    cur.next = prev2;
                    break;
                } 
            }
            return dummpy.next;
        }
    }

**复杂度分析**

*  **时间复杂度**： O ( N ∗ k ) O(N\*k) O(N∗k)
 *  **空间复杂度**:  O ( 1 ) O(1) O(1)

--------------------

**思路 \* 2**  
在循环中使用两个变量控制一下原来的链表中的一个节点和后面的一个节点。让第一个节点指向第二个节点的后面的节点，初始化一个头节点进行重新的遍历。

**代码 \* 2**

class Solution { 
        public ListNode swapPairs(ListNode head) { 
            ListNode cur = new ListNode(-1); 
            ListNode dummpy = cur;
            cur.next = head;
            while(cur.next != null && cur.next.next != null) { 
                ListNode first = cur.next;
                ListNode second = cur.next.next;
                first.next = second.next;
                cur.next = second;
                cur.next.next = first;
                cur = cur.next.next;
            }
            return dummpy.next;
        }
    }

**复杂度分析**

*  **时间复杂度**： O ( N ) O(N) O(N)
 *  **空间复杂度**:  O ( 1 ) O(1) O(1)

--------------------

**思路 \* 3**  
使用递归的方法。

**代码 \* 3**

class Solution { 
        public ListNode swapPairs(ListNode head){ 
          if(head == null || head.next == null) { 
              return head;
          }
          ListNode next = head.next;
          head.next = swapPairs(head.next.next);
            next.next = head;
            return next;
        }
    }

**复杂度分析**

*  **时间复杂度**： O ( N ) O(N) O(N)
 *  **空间复杂度**:  O ( N ) O(N) O(N)

--------------------

**完整代码**

package leetcode24;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    /** * Created by 张超帅 on 2018/10/16. */
    class ListNode { 
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }
    class Solution { 
        public ListNode swapPairs(ListNode head){ 
            ListNode cur = new ListNode(-1);
            ListNode dummpy = cur;
            cur.next = head;
            while(cur.next != null && cur.next.next != null) { 
                ListNode first = cur.next;
                ListNode second = cur.next.next;
                first.next = second.next;
                cur.next = second;
                cur.next.next = first;
                cur = cur.next.next;
            }
            return dummpy.next;
        }
    }
    public class leetcode24 { 
        public static int[] stringToArrays(String input){ 
            input = input.trim();
            input = input.substring(1, input.length() - 1);
            if(input == null) { 
                return new int[0];
            }
            String[] parts = input.split(",");
            int[] res = new int[parts.length];
            for(int i = 0; i < parts.length; i ++){ 
                res[i] = Integer.parseInt(parts[i]);
            }
            return res;
        }
        public static ListNode stringToListNode(String input) { 
            int[] nodes = stringToArrays(input);
            ListNode dummpy = new ListNode(-1);
            ListNode cur = dummpy;
            for(int node : nodes){ 
                cur.next = new ListNode(node);
                cur = cur.next;
            }
            return dummpy.next;
        }
        public static String listnodeToString(ListNode head){ 
            if(head == null) { 
                return "[]";
            }
            String res = "";
            while (head != null) { 
                res += head.val +", ";
                head = head.next;
            }
            return "[" + res.substring(0, res.length() - 2) + "]";
        }
        public static void main(String[] args) throws IOException { 
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String line;
            while((line = in.readLine()) != null) { 
                ListNode head = stringToListNode(line);
                ListNode ret = new Solution().swapPairs(head);
                String res = listnodeToString(ret);
                System.out.println(res);
            }
        }
    }