Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
给定一个链表，把相邻两个结点调换位置；返回head
Java代码：
1 package com.rust.cal; 2 3 /** 4 * Definition for singly-linked list. 5 * public class ListNode { 6 * int val; 7 * ListNode next; 8 * ListNode(int x) { val = x; } 9 * } 10 */ 11 public class SwapNodesinPairs { 12 public static ListNode swapPairs(ListNode head) { 13 if (head == null || head.next == null) { 14 //必须先判断head是否为null，否则会出java.lang.NullPointerException 15 //如果输入的head == null，先判断head.next会找不到目标 16 return head; 17 } 18 /* 针对前两个结点 */ 19 ListNode pre = head.next, later, veryFirst; 20 head.next = pre.next; 21 pre.next = head; 22 head = pre; 23 later = head.next; 24 /* 25 * 针对后续结点 26 * 连续有2个结点，才进行换位 27 */ 28 while (later.next != null && later.next.next != null) { 29 veryFirst = later; 30 pre = pre.next.next; 31 later = later.next.next; 32 pre.next = later.next; 33 later.next = pre; 34 veryFirst.next = later; 35 later = pre; 36 pre = veryFirst.next; 37 } 38 return head; 39 } 40 41 public static void main(String args[]){ 42 /* 43 * prepare data 44 */ 45 ListNode head = new ListNode(1); 46 ListNode initHead = head; 47 for (int i = 2; i < 10; i++) { 48 initHead.next = new ListNode(i); 49 initHead = initHead.next; 50 } 51 52 head = swapPairs(head); 53 /* 54 * show data 55 */ 56 ListNode newHead = head; 57 while(newHead != null){ 58 System.out.print(newHead.val + " "); 59 newHead = newHead.next; 60 } 61 ListNode nothing = new ListNode(1); 62 swapPairs(nothing.next); 63 } 64 }
输出：
2 1 4 3 6 5 8 7 9
这个方法是先处理前2个结点，再循环处理后续的结点。其实结点的处理方法都差不多，在LeetCode讨论区看到递归解法，搬运过来
Java代码：
public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode n1 = head; ListNode n2 = head.next; n1.next = n2.next; n2.next = n1; n1.next = swapPairs(n1.next); return n2; }
利用方法开头对head是否为null的判断作为递归的条件，比第一个方法优雅很多
