问题一、反转单链表 题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
链表结点定义如下,这里使用的是Java描述:
1 2 3 4 5 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
思路 如何把一个单链表进行反转?
方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。
方法2:用头插法新建链表。我们知道创建链表的两种方式:头插法 和尾插法 ,头结点插入法形成的链表是和输入顺序相反的,尾节点插入法形成的链表是和输入顺序相同的,所以其中一种方法是,遍历原链表,然后用原链表的输出元素顺序用头结点插入法新建链表,这样新建的链表就是反转后的链表。
方法3:就地反转链表。使用3个指针遍历单链表,逐个链接点进行反转。
1、借助数组逆序反转 由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static ListNode reverseList1 (ListNode head) { if (head == null ) return null ; List<ListNode> nodeList = new ArrayList<ListNode>(); while (head != null ) { nodeList.add(head); head = head.next; } int startIndex = nodeList.size() - 1 ; for (int i = startIndex; i >= 0 ; i--) { ListNode node = nodeList.get(i); if (i == 0 ) { node.next = null ; } else { node.next = nodeList.get(i - 1 ); } } head = nodeList.get(startIndex); return head; }
2、头插法新建链表来反转 这个方法和第一个借助数组一样,需要额外一倍的空间来存储生成的新链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static ListNode reverseList2 (ListNode head) { if (head == null ) return null ; ListNode previous = null ; ListNode newHead = null ; while (head != null ){ newHead = new ListNode(head.val); newHead.next = previous; previous = newHead; head = head.next; } return newHead; }
3、三个指针就地反转 使用三个指针指向:当前节点A,下个节点B,以及下下个节点C。
遍历时,如下首先记录下下个节点C,然后节点B的指针断开并指向A。然后移动进入下一组。
A -> B -> C ->D -> E
A <- B C ->D -> E
整个过程只需遍历链表一次,效率提高不少,且需要的外部空间也较第一种方法要少很多,实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static ListNode reverseList (ListNode head) { if (head == null ) return null ; ListNode a = head; ListNode b = head.next; ListNode temp; head.next = null ; while (b != null ){ temp = b.next; b.next = a; if (temp == null ){ break ; } a = b; b = temp; } return b == null ? a : b; }
单元测试 测试代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class Test { public static void main (String[] args) { ListNode a1 = new ListNode(5 ); ListNode a2 = new ListNode(4 ); ListNode a3 = new ListNode(30 ); ListNode a4 = new ListNode(78 ); ListNode a5 = new ListNode(99 ); a1.next = a2; a2.next = a3; a3.next = a4; a4.next = a5; ListNode node = reverseList(a1); while (node != null ){ System.out.print(node.val); node = node.next; System.out.print(node != null ? "->" : "" ); } } }
问题二、单链表两两反转 一个链表:a->b->c->d->e
每两个元素进行反转:b->a->d->c->e
输入:链表头指针 输出:反转后的链表头指针 要求:不新建节点
解答 仿照前面的单链表反转,我们最少需要三个指针: current,next, nextNext。 分析:我们需要两个“指针”指着当前要反转的两个值current和next。两两反转后,我们还需要记录下一个的值,即反转A和B后, 需要记录 C 值,我们才能够不断向下走,直到到达链表末端。所以,需要另一个指向下一个值的“指针”,即nextNext。反转以后,A的下一个是C, 但是,实际上,A的下一个应该是D ,所以,每次反转时,我们需要更新前一个值的下一个值,也就是说把 A -> C 改成 A -> D,所以需要prev指针。所以,要完成这个操作,我们总共需要4个“指针”。具体看代码: 所以最终我们一共需要分析四个指针: prev,current,next, nextNext。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public static ListNode reversePairedList (ListNode head) { if (head == null ) return null ; ListNode a = head; ListNode b = head.next; ListNode temp; ListNode previous = null ; ListNode newHead = b == null ? a : b; while (b != null ){ temp = b.next; b.next = a; a.next = temp; if (previous != null ){ previous.next = b; } if (temp == null ){ break ; } previous = a; a = temp; b = temp.next; } return newHead; }
参考资料