剑指 Offer 24. 两两交换链表中的节点

image.png

解题思路

非递归写法：（这图是基本原理）

image.png

head=head.next;保存链表，便于返回

TIM图片20200624114351.jpg

代码

/**
 * 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=new ListNode();
      ListNode cur=head;
      while (cur == null || cur.next == null) {
            return head;
        }
    head=head.next;//因为反转了，所以链表的头部是之前的下一个元素，比如：原来是1，现在是2
      while(cur!=null&&cur.next!=null){
          res.next=cur.next;
          cur.next=cur.next.next;//与下一对数字连在一起
          res.next.next=cur;

          res=res.next.next;//往前挪动位置
          cur=cur.next;
      }
       return head ;
    }
}