首页 > 代码库 > leetcode24,交换链表相邻的节点

leetcode24,交换链表相邻的节点

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.

 

对于这样链表交换的题目,我一般都有两种解法。

第一种,看链表每个节点带有的数据量,这道题带有只有一个value值,只有一个int值,所以我一开始的想法就是,不真实的交换节点,只是交换里面的数据。

这样的好处是空间复杂度特别省,适合那些每个节点数据很少,要求不高的链表交换。

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode swapPairs(ListNode head) {        if(head == null || head.next == null)            return head;                ListNode A = head;        ListNode B = head.next;                int t;        while(A != null && B != null){            t = B.val;            B.val = A.val;            A.val = t;                        if(B.next == null)                break;            A = B.next;            B = B.next.next;        }                return head;    }}

第二种解法就是真的去交换节点。

那么就需要多余的节点去记录当前结点的情况然后去交换

我用h,1,2,3这4个节点来说明。

123是原来的节点。

而h是头节点,指向1

 

下面是交换的步骤。

h->1->2->3

1->3(这个3通过2.next找)

h->2(这个直接有2)

h->->1(这个1也是直接有)

h->3(这个3通过1.next找)

技术分享

leetcode24,交换链表相邻的节点