Topic link

Leetcode-cn.com/problems/sw…

Topic describes

Given a linked list, swap adjacent nodes in pairs and return the swapped list.

You can’t just change the values inside a node, you need to actually swap nodes.

Example:

Given 1->2->3->4, you should return 2->1->4->3.Copy the code

The problem solving scheme

Train of thought

  • Tags: linked lists
  • In fact, the recursive and non-recursive solutions in this question are similar in principle. They both update the form of the linked list at every two points to complete the adjustment of the whole list
  • The recursive solution can be explained as a typical recursive solution

Recursive writing is to observe the solution process of this level of recursion and form an abstract model, because recursion is essentially the same thing over and over again. Instead of thinking about the whole call stack, level by level, you don’t know where to start. As shown in the figure, we should focus on the case of first-level calls to small units, namely a single f(x).

There are three main things we should be concerned about:

  1. The return value
  2. What does the calling unit do
  3. Termination conditions

In this case:

  1. Return value: The sublist of completed exchanges
  2. Call unit: Set the two points to be exchanged as head and next, head joins the sub-list to be swapped, and next joins HEAD to complete the swap
  3. Terminating condition: head is null or next is null, that is, there is currently no node or only one node and cannot be swapped

code

The recursive method

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        returnnext; }}Copy the code

Non-recursive solution

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next ! =null&& temp.next.next ! =null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        returnpre.next; }}Copy the code

Draw solution

Background reply “algorithm”, join every day algorithm group feel algorithm directly to the soul, welcome to click on and forward