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

1.题目描述

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

2.解题思路

方法1：将链表中的数放到stack里面，每当stack里面有两个值，就pop弹出，将弹出的值放到新的链表后面。

方法2：递归

3.代码

public static ListNode swapPairs(ListNode head) {
     Stack<Integer> stack = new Stack<>();
     ListNode res = new ListNode(-1);
     ListNode ans = res;
     while(head!=null){
         stack.push(head.val);
         head = head.next;
         if(stack.size()==2){
             while(!stack.isEmpty()){
                 res.next = new ListNode(stack.pop());
                 res = res.next;
             }
         }
     }
     while(!stack.isEmpty()){
         res.next = new ListNode(stack.pop());
         res = res.next;
     }
     return ans.next;
 }

方法2：

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

4.提交记录