题目

image.png

思路

  • 思路一：使用头插法来翻转节点

  • 思路二：使用递归翻转链表

    代码

    1.    public ListNode swapPairs(ListNode head) {
    2.       ListNode dummy = new ListNode(0);
    3.       dummy.next = head;
    4.       ListNode prv = dummy;
    5.       while (head != null && head.next != null) {
    6.           ListNode nex = head.next;
    7.           head.next = nex.next;
    8.           nex.next = prv.next;
    9.           prv.next = nex;
    10.           //重置节点
    11.           prv = head;
    12.           head = head.next;
    13.       }
    14.       return dummy.next;
    15.   }
    17.   //自己的递归
    18.   public ListNode swapPairs(ListNode head) {
    19.       if (head == null || head.next == null) return head;
    20.       ListNode nextHead = swapPairs(head.next.next);
    21.       ListNode nHead = reverse(head, 1);
    22.       nHead.next.next = nextHead;
    23.       return nHead;
    24.   }
    26.   public ListNode reverse(ListNode head, int i) {
    27.       if (i == 2) {
    28.           return head;
    29.       }
    30.       ListNode nHead = reverse(head.next, i + 1);
    31.       head.next.next = head;
    32.       head.next = null;
    33.       return nHead;
    34.   }
    36.   //别人的递归
    37.   public ListNode swapPairs(ListNode head) {
    38.       if (head == null || head.next == null) return head;
    39.       ListNode next = head.next;
    40.       head.next = swapPairs(head.next.next);
    41.       next.next = head;
    42.       return next;
    43.   }

    两两交换链表中的节点