> 电脑数码
如何把链表相邻元素翻转过来(如何把链表相邻元素翻转到一起)
导语:如何把链表相邻元素翻转
题目描述:
把链表相邻元素翻转,如给定链表为1->2->3->4->5->6->7,则翻转后的链表变为2->1->4->3->6->5->7
方法一:交换值法
这种方法由于不需要调整链表的结构,因此比较容易实现,但是这种方法并不是考官所期望的方法。
方法二:就地逆序
通过调整节点指针域的指向来直接调整相邻的两个结点。如果单链表恰好有偶数个节点,那么只需要将奇数偶数结点对调即可,如果链表有奇数个结点,那么只需要将最后一个结点外的其他结点进行奇数偶数对调即可。例如下图
当前遍历到结点cur,通过步骤(1)~(6),用虚线的指针来代替实线的指针实线相邻结点的逆序。其中,步骤(1)~(4)实现了前两个结点逆序操作,步骤5和6向后移动指针,接着可以采用同样的方式实现后面两个相邻结点的逆序操作。
public static void reverse(Node head) { if (head == null || head.next == null) { return; } Node cur = head.next; Node pre = head; Node next; while (cur != null && cur.next != null) { // 以下6行分别对应步骤1-6 next = cur.next.next; pre.next = cur.next; cur.next.next = cur; cur.next = next; pre = cur; cur = next; } } public static void main(String[] args) { int i = 1; Node head = new Node(); head.next = null; Node tmp = null; Node cur = head; for (;i<8;i++) { tmp = new Node(); tmp.value = i; tmp.next = null; cur.next = tmp; cur = tmp; } System.out.println(&34;); for (cur = head.next;cur != null;cur = cur.next) { System.out.print(cur.value + &34;); } reverse(head); System.out.println(&34;); for (cur = head.next;cur != null;cur = cur.next) { System.out.print(cur.value + &34;); }
算法性能分析
此方法只需要对链表遍历一次,时间复杂度为O(1),由于只需要几个指针变量保存节点地址,空间复杂度为O(1)。
本文内容由小娴整理编辑!