LeetCode--24. Swap Nodes in Pairs

系统管理员 2022-07-27 14:50 261阅读 0赞

Problem:

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis:
题目意思：

给定一个链表，调换每两个相邻节点，并返回其头部。
例如， 给定 1->2->3->4， 你应该返回的链表是 2->1->4->3。
你的算法必须使用唯一不变的空间。
你也不能修改列表中的值，只有节点本身是可以改变的。

链表问题，这个题需要多用一个节点，一个标记一对中的第一个，一个标记一对中的第二个。
Answer:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  11.     public ListNode swapPairs(ListNode head) {
  12.         if(head==null || head.next==null) return head;
  13.         ListNode pre=new ListNode(0);
  14.         pre.next= head;
  15.         ListNode p=pre;
  16.         while(p.next!=null && p.next.next!=null){
  17.             //
  18.             ListNode t1 = p;
  19.             p=p.next;
  20.             t1.next=p.next;
  21.             //
  22.             ListNode t2 = p.next;
  23.             p.next.next =p;
  24.             p.next=t2;
  25.         }
  26.         return pre.next;
  27.     }
  28. }

经验：

1.一般链表的问题如果会返回链表（从头开始）则最好用以下的三行代码，helper来记住链表开头，p来进行运算；而且p = helper后p和helper指向的下一个节点一致。

  1. ListNode helper = new ListNode(0);
  2.       helper.next = head;
  3.       ListNode p = helper;

2.p = p.next这句语句就是将p的指针后移（因为是对p操作的），p.next = t2这句与句就是把p的指向变换（因为是对p.next操作的），
p.next.next = p就是对p的下一个节点的指向操作。

3.while(p.next != null && p.next.next != null)这句语句来进行下一个节点是否满足情况的分析。

发表评论

表情：
评论列表 （有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读