【LeetCode每日一题】[中等]143. 重排链表

it2024-07-25  40

【LeetCode每日一题】[中等]143. 重排链表

143. 重排链表

题目来源 算法思想:链表

题目:

java代码–利用list

思路:借用额外的list存起来,像翻转数组一样,两指针,一前一后

class Solution { public void reorderList(ListNode head) { if (head == null) {//为空,直接返回 return; } List<ListNode> list = new ArrayList<ListNode>();//list ListNode tmp = head;//用来将结点存放至列表中 while (tmp != null) {//存放结点 list.add(tmp); tmp = tmp.next; } int i = 0; int j = list.size()-1; while (i < j) {//i指向头,j指向尾 list.get(i).next = list.get(j);//i的下一个指向j i++;//i向后移动 if (i == j) {//如果ij相遇,直接返回 break; } list.get(j).next = list.get(i);//j指向此时的i,完成插入 j--;//j向前移动 } list.get(i).next = null;//i指向的下一个为null,完成链表的重排 } }

java代码–直接分段,连接

思路:分成两段,将第二段逆转,然后插入第一段

class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode p1 = head; ListNode p2 = head; //统计链表长度 int count = 0; while (p2 != null) { count++; p2 = p2.next; } p2 = head; //遍历链表,找到要插入的后半部分(第二部分) int n = (count+1) / 2; while (n > 1) { n--; p1 = p1.next; p2 = p2.next; } //p2指向要插入的链表部分(第二部分) //将链表的前一部分(第一部分)末尾设置成null p2 = p2.next; p1.next = null; p1 = head;//p1指向第一部分头 //p2逆转(逆转第二部分) ListNode pre = null; while (p2 != null) { ListNode tmp = p2.next; p2.next = pre; pre = p2; p2 = tmp; } p2 = pre; //将第二部分插入第一部分 ListNode p11; ListNode p22; while (p2 != null) { p11 = p1.next; p22 = p2.next; p1.next = p2; p2.next = p11; p1 = p11; p2 = p22; } } }
最新回复(0)