golang力扣leetcode 143.重排链表

143.重排链表

143.重排链表

题解

1. 找到中点断开，翻转后面部分，然后合并前后两个链表
2. 重建该链表

两种实现方式

代码

package main

type ListNode struct {
	Val  int
	Next *ListNode
}
//找到中点断开，翻转后面部分，然后合并前后两个链表
func reorderList1(head *ListNode) {
	if head == nil {
		return
	}
	mid := findMiddle(head)

	tail := mid.Next
	mid.Next = nil

	tail = reverseList(tail)

	mergeTwoLists(head, tail)
}

//快慢指针找中点
func findMiddle(head *ListNode) *ListNode {
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

//翻转链表
func reverseList(head *ListNode) *ListNode {
	curr := head
	var p *ListNode
	for curr != nil {
		next := curr.Next
		curr.Next = p
		p = curr
		curr = next
	}
	return p
}

//l1链表插一个，l2链表插1个，依次添加
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	head := dummy
	var f bool = true
	for l1 != nil && l2 != nil {
		if f {
			head.Next = l1
			l1 = l1.Next
		} else {
			head.Next = l2
			l2 = l2.Next
		}
		f = !f
		head = head.Next
	}
	if l1 != nil {
		head.Next = l1
		l1 = l1.Next
		head = head.Next

	} else if l2 != nil {
		head.Next = l2
		l2 = l2.Next
		head = head.Next
	}
	return dummy.Next
}
//重建该链表
func reorderList2(head *ListNode) {
	if head == nil {
		return
	}
	var nodes []*ListNode
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}
	i, j := 0, len(nodes)-1
	for i < j {
		nodes[i].Next = nodes[j]
		i++
		if i == j {
			break
		}
		nodes[j].Next = nodes[i]
		j--
	}
	nodes[i].Next = nil
}

func main() {
	reorderList1(nil)
	reorderList2(nil)
}