白羊的空间

leetcode 24

力扣24题的两种解法

可以采用递归和非递归两种思路解题，其实两种思路类似，都是分块两两解决。

递归方法

  1. 首先假设swapPairs方法已经存在并能解决问题；
    1
    2
    3
    func swapPairs(head *ListNode) *ListNode{
        ...
    }
  2. 找到结束条件
    因为是两两交换，那么head不存在或者head的下一个节点不存在就说明已经没有可以交换的节点了，直接返回head即可;
    1
    2
    3
    if head == nil || head.Next == nil {
        return head
    }
  3. 单次交换步骤
    1. 找到head的下一节点 next := head.Next
    2. 将head的下一节点设置为next节点后面的节点，我们把next节点后面的节点next.Next单独看成一个链表的头节点，那么只需要用swapPairs处理后面的节点即可:
      1
      head.Next := swapPairs(next.Next)
    3. 最后把next节点的下一个节点指向head节点就交换完成了:
      1
      next.Next = head
  4. 找到返回值
    因为swapPairs方法的目的是两两交换，那么交换后，next节点就是交换后的头节点了，返回next节点即可：
    1
    return next
    下面是完整代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func swapPairs(head *ListNode) *ListNode {
    	if head == nil || head.Next == nil {
    		return head
    	}
    	next := head.Next
    	head.Next = swapPairs(next.Next)
    	next.Next = head
    	return next
    }

非递归方法

非递归采用三个指针，分别

  1. 指向当前组的第一个节点的curr
  2. 指向curr上一个节点的prev
  3. 指向下一组第一个节点的next

循环开始条件,当前节点不为空并且下一节点也不为空：

1
curr != nil && curr.Next != nil

单次循环交换步骤

  1. 记录下一组第一个节点next:
  2. 把prev下一个节点指向curr的下一个节点
  3. 把curr.Next下一个节点指向curr节点
  4. 把curr的下一节点指向下一组的第一个节点完成交换
  5. 修改prev指针指向curr，即为下一组第一个节点的上一个节点
  6. 修改curr指针指向next，即为下一组第一个节点
  7. 循环完成

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func swapPairs(head *ListNode) *ListNode {
	forward := &ListNode{Next: head}
	prev := forward
	curr := forward.Next
	for curr != nil && curr.Next != nil {
		next := curr.Next.Next // 记录下一组第一个节点`next`:
        
		prev.Next = curr.Next  // 把`prev`下一个节点指向`curr`的下一个节点
		curr.Next.Next = curr  // 把`curr.Next`下一个节点指向`curr`节点
		curr.Next = next       // 把`curr`的下一节点指向下一组的第一个节点完成交换
        
		prev = curr            // 修改`prev`指针指向`curr`，即为下一组第一个节点的上一个节点
		curr = next            // 修改`curr`指针指向`next`，即为下一组第一个节点
	}
	return forward.Next
}
leetcode leetcode