两两交换链表中的节点

24. 两两交换链表中的节点

1.想法：

这个题重要的是保证下一个做两两交换的节点首先被缓存了。例如：

image.png

对于1，2节点来说我们要现在交换，但是如果交换后3就找不到，所以必须先把3记录了，然后再去把1，2交换
，等1，2交换了变成了2，1，然后让1指向3，4交换后的节点就好了。
那么我们现在设现在要交换的节点是newNode（相当于1，和后来的3们）用next表示newNode的下一个节点（相当于2，和后来的4），那么什么时候停止呢？我们可以有一下的总结：

那么我们就可以写出代码了

2.代码：

递归写法：(下面的代码中字母对应上面分类中的字母，情况一致）

public ListNode swapPairs(ListNode head) {
         if(head == null||head.next==null)return head;   //A
         else{
             if(head!=null){                  
                 if(head.next!=null) {  
                     ListNode next = head.next;
                     if(head.next.next!=null) {       //D
                         ListNode newHead = head.next.next;
                         next.next = head;
                         head.next = MySwapHead(newHead);
                     }else{                         //C
                         next.next = head;
                         head.next = null;
                     }
                     return next;
                 }else{
                     return head;    //B
                 }
             }else{
                 return head;  //A
             }
         }
    }

迭代写法：

 public ListNode swapPairs(ListNode head) {
         if(head == null||head.next==null)return head;
         else{
             ListNode newHead = head.next;
             ListNode last=null,nownext=newHead,nowheir=null;
             while(head!=null){
                 if(head.next!=null) {
                     if (head.next.next != null) {
                         nowheir = head.next.next;
                         nownext = head.next;
                         nownext.next = head;
                         if(last!=null) {
                             last.next = nownext;
                         }
                         last = head;
                         head = nowheir;
                     } else {
                         nownext = head.next;
                         nownext.next = head;
                         if(last!=null) {
                             last.next = nownext;
                         }
                         break;
                     }
                 }else{
                     last.next = head;
                     break;
                 }

             }
            
             return newHead;
         }
    }

不知道为什么运行超时？