首页 > 代码库 > 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,交换链表相邻的节点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。