搜索
写经验 领红包

如何把链表相邻元素翻转过来(如何把链表相邻元素翻转到一起)

导语:如何把链表相邻元素翻转

题目描述:

把链表相邻元素翻转,如给定链表为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)。

本文内容由小娴整理编辑!