24.两两交换链表中的节点_力扣_算法

• 思路一
  单向链表,而且不确定长度的交换,那必须使用递归了.
  递归的话,一个是递归的入口,另一个是递归的出口.
  先慢慢的往下交换几个, 试试入口在哪. 经调试,发现入口在链表长度为4以上的地方,这时会出现一个拐点情况: 2->1->4, 而且3->4 .出现了两条岔路,明显前面那条岔路是正确的, 只需要将后面那条岔路放进去递归调整就可以了.而且会发现3->4 像极了初始时1->2的场景.这就是递归的入口.
  出口就是没有子节点后,自动出来了,当然,要注意的是,当只有2个节点的时候,需要注意将头节点的子节点指向空的,不然死循环了.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode res;
        if(head !=null ){
            if(head.next != null){
                res = head.next;
            }else {
                res = head;
            }
            this.dg(head,res);
            return res;
        }else{
            return null;
        }
    }
    //取调整顺序的链表的根节点的标志
    boolean flag = true;
    private void dg(ListNode head,ListNode res){
        if(head.next != null){
            ListNode sec = head.next;
            if(sec.next != null){
                ListNode third = sec.next;
                sec.next = head;
                if(third.next!=null){
                    ListNode fou = third.next;
                    head.next = fou;
                    this.dg(third,res);
                }else {
                    head.next=third;
                }
            }else {
                sec.next = head;
                //此处指向空,不然死循环,跳不出去.
                head.next = null;
                if(flag){
                    res = sec;
                    flag = false;
                }
            }
        }
    }
}